6 line java solution


  • 2
    J

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


  • 0
    S

    Good solution. Adding comments:

    f[i] keeps track of whether a substring from [0 to i) satisfies wordBreak given the current dictionary.

    f[0] is the empty string and the empty string satisfies wordBreak.

    This statement, f[j] && wordDict.contains(s.substring(j, i)), checks whether substring A AND substring B satisfies wordBreak.

    • i is the variable that is the current index for splitting s.

    • j is the variable that creates two substrings: from substring A: [0 to j) and substring B: [j to i) of s.

    f[i] |= ... uses the inclusive or. If true, then that means that there are at least two substrings, from [0 to j) and [j to i) in s that satisfy wordBreak.

    Hope that helps!


Log in to reply
 

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