Java 1ms solution using dynamic programming


  • 2
    A
    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            boolean[] possible = new boolean[s.length()];
            if (wordDict.contains(s.substring(0, 1)) == true) possible[0] = true;
            for (int i = 1; i <= s.length() - 1; i++) {
                for (int j = i ; j >= 0; j--) {
                    if (j > 0 && possible[j - 1] == true && wordDict.contains(s.substring(j, i + 1)) == true) {
                        possible[i] = true;
                        break;
                    } else if (j == 0 && wordDict.contains(s.substring(0, i + 1)) == true) {
                        possible[i] = true;
                        break;
                    }
                }
            }
            return possible[s.length() - 1] == true;
        }
    }

  • 0
    E

    Very nice solution. I modified it a little bit following your algorithm:

    public boolean wordBreak(String s, Set<String> wordDict) {
        int L = s.length();
        boolean[] possible = new boolean[L+1];
        possible[0] = true;
        for (int i=0; i<=L; i++) {
            for (int j=i ; j>=1; j--) {
                if (possible[j-1] && wordDict.contains(s.substring(j-1,i))) {
                    possible[i] = true;
                    break;
                }
            }
        }
        return possible[s.length()];
    }

  • 0
    A

    Cool, I like your solution too,


Log in to reply
 

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