139. Word Break

三刷 06/2022
Version #1 DP

Time O(N^3) - substring also takes O(N) time

Space O(N)

Runtime: 9 ms, faster than 61.58% of Java online submissions for Word Break.

Memory Usage: 45.2 MB, less than 53.48% of Java online submissions for Word Break.

class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {

        Set<String> wordSet = new HashSet<>(wordDict);

        // dp[i] - If substring [0, i) can be segmented into a space-separated sequence

        boolean[] dp = new boolean[s.length() + 1];

        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {

            for (int j = i - 1; j >= 0; j--) {

                if (wordSet.contains(s.substring(j, i)) && dp[j]) {

                    dp[i] = true;

                    break;

                }

            }

        }

        return dp[s.length()];

    }

}

Version #2 Memorized DFS
二刷
发现mem[index] = true是没有意义的，因为只要发现true就会立刻返回
所以把mem Boolean 改成visited boolean，只要之前visit过证明一定是false的
40.30 %

//mem[i] Boolean[] - index [i, length) can break
public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || wordDict == null) throw new IllegalArgumentException();
        boolean[] visited = new boolean[s.length()];
        //TODO
        return wordBreak(0, s, wordDict, visited);
    }
    private boolean wordBreak(int index, String s, List<String> wordDict, boolean[] visited) {
        if (index == s.length()) return true;
        if (visited[index]) return false;
        String word;
        for (int i = index; i <= s.length(); i++) {
            word = s.substring(index, i);
            if(wordDict.contains(word) && wordBreak(i, s, wordDict, visited)) {
                return true;
            }
        }
        visited[index] = true;
        return false;
    }
}

O(n^2)
45.96 %
//mem[i] Boolean[] - index [i, length) can break
public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || wordDict == null) throw new IllegalArgumentException();
        Boolean[] mem = new Boolean[s.length()];
        //TODO
        return wordBreak(0, s, wordDict, mem);
    }
    private boolean wordBreak(int index, String s, List<String> wordDict, Boolean[] mem) {
        if (index == s.length()) return true;
        if (mem[index] != null) return mem[index];
        String word;
        for (int i = index; i <= s.length(); i++) {
            word = s.substring(index, i);
            if(wordDict.contains(word) && wordBreak(i, s, wordDict, mem)) {
                mem[index] = true;
                return true;
            }
        }
        mem[index] = false;
        return false;
    }
}

Version #1 DP
82.51 %

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) return false;
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int fast = 1; fast <= s.length(); fast++) {
            for (int slow = fast - 1; slow >= 0; slow--) {
                if (dp[slow] && wordDict.contains(s.substring(slow, fast))) {
                    dp[fast] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}