leetCode/leetCode_139.java at master · mehtabgill/leetCode · GitHub

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
45
46
47
48
49
50
51
52
53
54
// class Solution {
//     public boolean wordBreak(String s, List<String> wordDict) {
//         int n = s.length();
//         boolean dp[] = new boolean[n];
//         HashSet<String> set = new HashSet<>();
//         for(String ss: wordDict){
//             set.add(ss);
//         }
//         for(int i=0; i<n; i++){
//             if(dp[i] == false && set.contains(s.substring(0, i+1))){
//                 dp[i] = true;
//             }
//             if(dp[i]){
//                 if(i == n-1){
//                     return true;
//                 }
//                 for(int j=i+1; j<n ; j++){
//                     if(dp[j]==false && set.contains(s.substring(i+1, j+1))){
//                         dp[j] = true;
//                     }
//                     if(dp[j] && j == n-1){
//                          return true;
//                     }
//                 }

//             }
//         }

//         return false;
//     }
// }

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean dp[] = new boolean[n+1];
        HashSet<String> set = new HashSet<>();
        for(String ss: wordDict){
            set.add(ss);
        }
        dp[0] = true;
        for(int i=1; i<=n; i++){
            for(int j=0; j<i;j++){
                if(dp[j] && set.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }

        }

        return dp[n];
    }
}