Leetcode - Word Break

[题目]

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

[分析] 摘自http://blog.csdn.net/linhuanmars/article/details/22358863

动态规划三步走法：首先，考虑解决问题过程中需要存储什么历史信息并采用何种数据结构合理；然后最关键的一步，推导递推关系式，即如何利用历史信息将问题推进解决，更具体地说如何获得当前状态；最后思考初始化条件。 

[tips] 用StringBuilder只需要调用一次substring(), 因此version3实现耗时要远小于version1 & 2

public class Solution {
    // version 3
    // 历史信息：dp[i] 表示s.substring(0, i)能否用dict中的词汇表示
    // 递推式：dp[i] |= dp[j] & dict.contains(s.substring(j,i)), 其中0 <= j < i
    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null || s.length() == 0)
            return false;
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            StringBuilder sub = new StringBuilder(s.substring(0, i));
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(sub.toString())) {
                    dp[i] = true;
                    break;
                }
                sub.deleteCharAt(0);
            }
        }
        return dp[n];
    }
}

 

public class Solution {
    // version 1： 二维数组保存历史信息
    public boolean wordBreak(String s, Set<String> dict) {
        //思路1：遍历dict，寻找能成为当前子串前缀的单词，递归判断剩余子串。大数据超时！
        //思路2：动态规划。回溯时有重复计算。f[i,j] |= f[i, k-1] && f[k, j] (i < k <= j), 
        if(s == null)
            return false;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n - 1; i >= 0; i--){
            dp[i][i] = dict.contains(s.substring(i, i + 1));
            for(int j = i + 1; j < n; j++){
                dp[i][j] = dict.contains(s.substring(i, j + 1));
                if(dp[i][j])
                    continue;
                for(int k = i; k < n; k++){
                    dp[i][j] |= dp[i][k] && dp[k + 1][j];
                    if(dp[i][j])
                        break;
                }
            }
        }
        return dp[0][n-1];
    }
    
    // 一维数组
    public boolean wordBreak(String s, Set<String> dict) {
        //思路2：动态规划。回溯时有重复计算。dp[i] = dict.contains(s(i, k)) && dp[k] 
        if(s == null)
            return false;
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[n] = true;
        for(int i = n - 1; i >= 0; i--){
            for(int k = i + 1; k <= n; k++){
                dp[i]= dict.contains(s.substring(i,k)) && dp[k];
                if(dp[i])
                    break;
            }
        }
        return dp[0];
    }
    
}

 

评论

3 楼 qb_2008 2015-04-03  

for (int i = 0; i < n; ++i) {
   for (int j = i; j < n; ++j) {
      if (dict.contains(s.substring(i, j + 1))) {
         dp[i][j] = true;
      }
   }
}

上面这段代码为什么是O(n^3)呢？很简单，判断一下dict.contains(s.substring(i, j+1))
的时间复杂度就行了。一个是s.substring(i, j+1)，一个是dict.contains(sub_s)。
s.substring(i, j+1)的时间复杂度必定是O(n)，因为要拷贝O(n)长度的子串。
dict.contains(sub_s)的时间复杂度应该至少是O(n)，虽然说dict在用hash表实现下是
O(1)的，但现在我们的key值就是一个O(n)长度的string，光把string翻译成整型的hash值
就要O(n)，完了最后肯定要比较一下sub_s是否和存在dict中的string相同，也是要O(n)的
吧。

动态规划的题目算是难的，很多动态规划的题目我也不会做。我做动态规划的题目，就是看
问题长度为1的时候怎么做，长度为2的时候怎么做，然后考虑怎样用已经解决的子问题去
解决更大长度的问题。这样自底向上的方式应该比较好想。这个也是有办法学的，先能看懂
分析，看懂代码，然后自己分析，自己写代码，多遇到一些同类的题目，就熟练了。

2 楼 likesky3 2015-04-03  

希望有一天我也能这么清楚到位得描述出自己的思路，看了你的分析后对这题理解得更多些了。因House Robber再次意识到动态规划类型题目自己远未掌握好，开始先练习这个类型。这道题目自己未想明白动归思路，暴力解超时，看了网上和自己先前的做法（也不知道是不是自己想出来的），只是表面上理解了解法的正确性，知其所然状态，并未想明白思路是怎么来的。另外，我不明白为什么你说第一步是O(n^3)，是把s.substring(i, j+1)的时间复杂度也算入吗？

1 楼 qb_2008 2015-04-02  

三个方法都很高效。我的思路是这样的：
这像一个字符串匹配，我把它看成一个字符数组，要匹配s[0, n-1].
现在要把字典中的word一个个贴上去，把整个字符数组match。
第一步是看字符串s中哪些子串可以用一个字典word匹配，然后才是
纯粹的动态规划。分成两步写，以保证正确。

public class Solution {
  public boolean wordBreak(String s, Set<String> dict) {
    int n = s.length();
    // dp[i][j] = true if s[i, j] can be matched by words in the dictionary.
    boolean[][] dp = new boolean[n][n];

    // Find dp[i][j] that can be matched by a single word.
    for (int i = 0; i < n; ++i) {
      for (int j = i; j < n; ++j) {
        if (dict.contains(s.substring(i, j + 1))) {
          dp[i][j] = true;
        }
      }
    }

    // dp[i][j] |= {dp[i][k] && dp[k + 1][j], for i <= k < j}
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        for (int k = i; k < j; ++k) {
          if (dp[i][k] && dp[k + 1][j]) {
            dp[i][j] = true;
          }
        }
      }
    }

    return dp[0][n-1];
  }
}

这个效率是低，都O(n^3)了，但它是正确的，而且更简单。我们可以在这个基础上
继续优化。

二维动态规划的时间复杂度一般都是O(n^3)，但这道题可以降为一维动态规划。
因为最终问的是dp[0][n-1]。那我们可以把递推式一头堵住，变为
dp[0][j] |= {dp[0][k] && dp[k + 1][j], for 0 <= k < j}.我们取最大的那个可行k值，那就是看
dict.contains(s[k+1, j])是否存在.

public class Solution {
  public boolean wordBreak(String s, Set<String> dict) {
    int n = s.length();

    // m[i][j] is true if s[i, j] can be matched by a single word in the dictionary.
    boolean[][] m = new boolean[n][n];
    for (int i = 0; i < n; ++i) {
      for (int j = i; j < n; ++j) {
        if (dict.contains(s.substring(i, j+1))) {
          m[i][j] = true;
        }
      }
    }

    // dp[i] is true if s[0, i] can be matched by words in the dictionary.
    boolean[] dp = new boolean[n];

    for (int i = 0; i < n; ++i) {
      dp[i] = m[0][i];

      // dp[i] |= {dp[j] && m[j + 1][i], for 0 <= j < i}
      for (int j = 0; j < i; ++j) {
        if (dp[j] && m[j + 1][i]) {
          dp[i] = true;
        }
      }
    }
    return dp[n - 1];
  }
}

上面的代码看起来对第二步的动态规划做了优化，从O(n^3)降为了O(n^2)。可惜第一步仍是O(n^3)的，所以
总的时间复杂度未变。所以在优化第一步之前，我们的解法并没有根本上的性能提升。如果把字典变成字典树
结构（Trie)，时间复杂度就可以从O(n^3)降为O(nk)，k是字典中最长单词的长度。如果感兴趣，可以实现一下
字典树，对字符串查找的性能提升很高哦。