[Leetcode] 139. Word Break | 单词拆分

yPhantom 2020年02月13日 35次浏览

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

一道word break经典问题。这种问题之前总是记不住。实际上就是采用dp的方法。下面比较一下两种写法的区别:

最简单的版本:

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

效率比较低,在leetcode中花了7ms,总共打败了30%+的人。

而下面这种利用前缀字符串的写法

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] v = new boolean[len+1];
        v[0] = true;

        for(int i = 0;i<len;i++){
            if(!v[i])
                continue;

            String substr = s.substring(i);
            for(String word:wordDict){
                if(substr.startsWith(word)){
                    v[ i + word.length()] = true;
                }
            }
        }

        return v[len];
    }
}

效率极高,只用了2ms。

Runtime: 2 ms, faster than 94.21% of Java online submissions for Word Break.
Memory Usage: 37.5 MB, less than 25.36% of Java online submissions for Word Break.

在第一种dp写法中,时间复杂度是1 + 2 + 3 + ... + n,是O(n2)的时间复杂度,在第二种方法中是O(m*n)。