139. Word Break

解法一

思路

To find out whether a word can be broken, we can check if itself is in the dict, or any of its segmentation is can be broken and the other part is in the dictionary.

For example, wordBreak("leetcode") = dict("leetcode") || wordBreak("l") && inDict("eetcode") || ... || wordBreak("leet") && inDict("code") || ...

So we can construct a recursion based on this. But this method does many duplicates check. For example, when we check wordBreak("leet"), it will check all segmentation of "leet" again, so it defnitely can be optimized by memoization. But let us write the original recursion first.

代码

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> wordSet = new HashSet<>(wordDict);
        return wordBreakHelper(s, wordSet);
    }

    private boolean wordBreakHelper(String s, Set<String> wordSet) {
        // If length of s is 0, of course it can be broken.
        if (s.length() == 0) {
            return true;
        }
        for (int i = 0; i < s.length(); i++) {
            String left = s.substring(0, i);
            String right = s.substring(i, s.length());
            // Don't forget you are calling wordBreakHelper, not wordBreak !!!
            if (wordBreakHelper(left, wordSet) && wordSet.contains(right)) {
                return true;
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度
  O(2^n), see Proof.
• 空间复杂度
  O(n), if all single character contains in wordDict.

解法二

思路

We can actually store the checked results of whether a segmentation of a string can be broken, so that every time we need to check it again, we can just retrive the results. I will use a hashmap, the segmentation of the string as key, and boolean as value to indicate whether it can be segemented.

代码

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> wordSet = new HashSet<>(wordDict);
        HashMap<String, Boolean> checkBreak = new HashMap<>();

        return wordBreakHelper(s, wordSet, checkBreak);
    }

    private boolean wordBreakHelper(String s, HashSet<String> wordSet, HashMap<String, Boolean> checkBreak) {
        if (s.length() == 0) {
            return true;
        }

        if (checkBreak.containsKey(s)) {
            return checkBreak.get(s);
        }

        for (int i = 0; i < s.length(); i++) {
            String left = s.substring(0, i);
            String right = s.substring(i, s.length());
            // 这里很关键 -- 如果 s 有任意的 segmentation 可分并且剩余部分在字典，那么它本身也可分！
            // 这就是为什么把（s, true）存到字典里。
            if (wordBreakHelper(left, wordSet, checkBreak) && wordSet.contains(right)) {
                checkBreak.put(s, true);
                return true;
            }
        }
        // 如果没有任何部分可分，就把 (s, false) 存进字典。
        checkBreak.put(s, false);
        return false;
    }
}

复杂度分析

• 时间复杂度
  O(n^2)
• 空间复杂度
  O(n)

解法三

思路

To solve this, we can solve some subproblems first. Let d[i] denote whether substring from 0 to i (not including i) can be broken, then d[i] == d[0] && inDict(0,i) || d[1] && inDict(1,i) || d[j] && inDict(j, i) || .. || d[i - 1] && inDict(i - 1, i), where 0 <= j < i.
If any of the condition satisfies, then we can return true.

代码

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] d = new boolean[s.length() + 1];
        // 关键
        d[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                d[i] = d[j] && set.contains(s.substring(j, i));
                if (d[i]) {
                    break;
                }
            }
        }
        return d[s.length()];
    }
}

Takeaway

本作品采用《CC 协议》，转载必须注明作者和本文链接