The tag for this question is dynamic programming. But using dynamic programming can't pass.


  • 0
    O

    I know others have better solutions using BFS or DFS. However, I first solved this problem using dynamic programming and I didn't check the tag at that time. I tested on my local machine and the result was correct and I submitted my solution but I didn't even pass the first test case. It gives me an error message of "time exceeded". I am wondering if there is a better way of using dynamic programming.

    Basically, what I did was to start from the first character of the string and test if it can be formed from strings in the set. I also use a boolean array to save this information then I add the next character from the string and test and so forth. Below is my code.

    public boolean wordBreak(String s, Set<String> dict) {
    	if (s==null) return false;
    	if (s.equals("")) return false;
    	int size=s.length();
    	boolean[] contained=new boolean[s.length()+1];
    	contained[0]=true;
    	for (int i=0;i<size;i++){
    		for (int j=i;j>=0;j--){
    			if (dict.contains(s.substring(j,i+1))&&contained[j]){
    				contained[i+1]=true;
    				break;
    			}
    			contained[i+1]=false;
    		}
    		
    	}
    	return contained[size];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.