139. Word Break

Posted on | Edited on | Views:

https://leetcode.com/problems/word-break/

My solution: recursion and backtracking —> Time Limit Exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public static boolean wordBreak(String s, List<String> wordDict) {
        return util(0,s,new HashSet(wordDict));   
    }
    
    public static boolean util(int start, String s, Set<String> wordDict){
        if(start==s.length()){
            return true;
        }else{
            for(int i=start;i<s.length();i++){
                if((wordDict.contains(s.substring(start,i+1)))&&util(i+1,s,wordDict)){
                    return true;
                }
            }
        }
        return false;
    }
}
/*class Solution {
    Boolean flag=false;

    public boolean wordBreak(String s, List<String> wordDict) {
        util(0,s,wordDict);
        return flag;
    }
    
    public void util(int start, String s, List<String> wordDict){
        if(start==s.length()){
            flag=true;
        }else{
            for(int i=start;i<s.length();i++){
                if(isInWordDict(start,i,s,wordDict)){
                    util(i+1,s,wordDict);
                    if(flag) return;
                }
            }
        }
    }

    public boolean isInWordDict(int start, int end, String s, List<String> wordDict){
        String subStr=s.substring(start,end+1);
        return wordDict.contains(subStr);
    }
}*/

DP: Top Down —> Recursion with memoization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return util(0,s,new HashSet(wordDict),new Boolean[s.length()+1]);
    }
    public boolean util(int start,String s,Set<String> wordDict,Boolean[] memo){
        if(start==s.length()) return true;
        if(memo[start]!=null) return memo[start];
        boolean isWord=false;
        for(int i=start;i<s.length();i++){
            if(wordDict.contains(s.substring(start,i+1))&&util(i+1,s,wordDict,memo)){
                return isWord=true;
            }
        }
        memo[start]=isWord;
        return isWord;
    }
}

DP: Bottom Up —> Tabulation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet=new HashSet(wordDict);
        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;
        for(int i=0;i<s.length();i++){
            for(int j=0;j<=i;j++){
                if(dp[j]&&wordDictSet.contains(s.substring(j,i+1))){
                    dp[i+1]=true;
                    break; //dp[i+1]=true, then move to the next character.
                }
            }
        }
        return dp[s.length()];
    }
}

LeetCode: Breadth-First-Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[s.length()];
        queue.offer(0);
        while (!queue.isEmpty()) {
            int start = queue.poll();
            if (!visited[start]) {
                for (int i = start; i < s.length(); i++) {
                    if (wordDict.contains(s.substring(start, i+1))) {
                        queue.offer(i+1);
                        if (i+1 == s.length()) return true;
                    }
                }
                visited[start] = true;
            }
        }
        return false;
    }
}

LeetCode: Depth-First-Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        LinkedList<Integer> stack = new LinkedList<>();
        int[] visited = new int[s.length()];
        stack.push(0);
        while (!stack.isEmpty()) {
            int start = stack.pop();
            if (visited[start] == 0) {
                for (int i = start; i < s.length(); i++) {
                    if (wordDict.contains(s.substring(start, i+1))) {
                        stack.push(i+1);
                        if (i+1 == s.length()) return true;
                    }
                }
                visited[start] = 1;
            }
        }
        return false;
    }
}

Recursion with flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public static boolean wordBreak(String s, List<String> wordDict) {
        return util(0,s,wordDict,new boolean[s.length()]);   
    }
    
    public static boolean util(int start, String s, List<String> wordDict,boolean[] visited){
        if(start==s.length()){
            return true;
        }else if(!visited[start]){// if from start can't reach the end then ignore the start position!
            for(int i=start;i<s.length();i++){
                if((wordDict.contains(s.substring(start,i+1)))&&util(i+1,s,wordDict,visited)){
                    return true;
                }
            }
            visited[start]=true;
        }
        return false;
    }
}

0%