Word Break

Leave a comment

November 6, 2016 by oneOokay

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".


这题好多种解法,每种都值得好好看看:TODO:要注意看一下他们的时间复杂度。

四种解法:普通DP,DP with Trie, DFS, BFS。

一、普通DP:首先应该想到DP:DP的时间复杂度是K^2,空间复杂度是K+1(K为string的长度)

先想是怎么样一定一个dp:容易先想到二维boolean[][]代表从i到j这个区间内的substring是能够被workbreak的,那么最终要求的是从dp[0][s.length()]。
这个可以优化成一维boolean[i]代表在index为i的char之前切一刀,它之前的substring是可以被wordbreak的,最终求dp[s.length()]。
dp推导公式:最后一步:dp[n]会等于dp[i]&&从charAt(index = i)到最后一个字符的substring是否存在于wordDict中,其中i的范围为从0到n-1。
所以是两个for loop:第一个for-loop来移动i(1-n):遍历dp[i]; 第二个for-loop在0-(i-1)内移动对dp[j]和j-i的substring进行判断,从而求得dp[i]。
(其实可以从后往前扫,这样就变成了求dp[0])

注意C#和java的区别:

  • java: s.substring(startIndex, endIndex): startIndex: inclusive; endIndex: exclusive.
  • C#: s.subString( startIndex, length)
  • dp[]: dp[i]表示到string index = i之前的substring都能够满足wordbreak的条件。
  • 递推关系是: dp[j]满足wordbreak的条件是:dp[i]满足且string.substring(i,j)也存在于dictionary中。
  • 优化点:
    • 扫描整个dict得到string的maxlen;
    • 一旦找到一个可分割,直接break,因为不需要求所有解在workbreakI中。II就不行。
public boolean wordBreak(String s, Set<String> wordDict) {     
    int length = s.length();
//因为第一个char要依靠一个不存在的前面的char,所以会把dp[0]=true.
//那么dp的长度就应该是length + 1
    boolean[] dp = new boolean[length + 1];
    dp[0] = true;//dp[0]初始化为true,因为dp[1]要靠这个
    int maxLength = 0;//优化.得到wordDict中最长的word的长度.
    for(String t : wordDict){
       maxLength = Math.max(maxLength, t.length());
    }

    for (int i = 1; i <= length; i ++){ 
//求dp[i]:因为dp[0]=true,所以从dp[1]开始.表示在index=i的char之前切一刀
//既然要求dp[i]的话,那么要对0-(i-1)进行判断,看是否存一个j:
//使得dp[j]=true并且从j-(i-1)的substring存在于wordDict中.
        for(int j = 0; j < i; j ++){ //j从index = 0开始;因为s.substring(j,i)
j<i确保了substring不为空(其实j==i也是没有问题的因为“”不存在于dict中)
//这里不能break,因为随着j变大,i-j是逐渐变小的
            if(i - j > maxLength) continue;
            if(dp[j] && wordDict.contains(s.substring(j, i))){
                dp[i] = true;
                break;//优化
            }
        }
     }
     return dp[length];
    }

二、DP with Trie:主要是熟悉一下Trie吧,以及用Trie的时候对string的扫描方式。这里用Trie来代替str.substring()是否存在于dict中。

想到了build trie,但是想不出如何在trie里面search以及剪枝.没有联想到boolean[]dp(这个恰巧在dfs里面想到了=.=) 04/28/2017

Trie:可以用来词频统计和前缀匹配。用Trie的前缀匹配的这个就可以代替在set中找substring是否存在。

定义TrieNode:里头必须要有的是一个TrieNode[] array;外加一个boolean来表示该点的path是否是一个存在于set里面的词。另外需要定义一个addWord method来加入word的同时(TrieNode[])对额外的attribute进行update,这里就是update boolean isWord。

注意用Trie的话就一定要从后往前扫描string了,

  • 如果从前往后扫的话:需要三层forloop:外层i:1-n求dp;中间层j:0-i找到dp[j];最里层k:j-i来在trie里找词
  • 如果从后往前扫的话:两层forloop:外层i:n – 1 到0求dp;内层j:i-n找到dp[j]的同时可以从trie里面找词(因为Trie是始终要从word的第一个词开始的)
 public class TrieNode{
        TrieNode[] c;
        boolean isWord;
        public TrieNode(){
            isWord = false;
            c = new TrieNode[128];
        }
    }
    
    public void addWord(TrieNode t, String s){
        for (int i = 0; i < s.length(); i ++){
            int index = (int)s.charAt(i);
            if (t.c[index] == null){
                t.c[index] = new TrieNode();
            }
            t = t.c[index];
        }
        t.isWord = true;//update attribute
    }
    public boolean wordBreak(String s, Set wordDict) {
        TrieNode t = new TrieNode();
        for(String w : wordDict){
            addWord(t, w);    
        }
        boolean[] dp = new boolean[s.length() + 1];
        dp[s.length()] = true;//由于从后往前扫:所以最后一个初始化为true
        for(int i = s.length() - 1; i >= 0; i --){
            TrieNode cur = t;
            for (int j = i; cur != null && j < s.length(); j ++){
//这里要判定cur是否为null,cur在forloop里面是不断进行迭代更新的
                cur = cur.c[(int)s.charAt(j)];
                if (dp[j + 1] && cur != null && cur.isWord){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }

三、DFS:用DFS+Memorizing不是DFS+Backtracking。time complexity?

能够第一个想到dfs,但是用了boolean[] isWord的dfs brutal force来做(最终返回isWord[s.length()].TLE,意识到需要剪枝,但是没有figure out 如何剪枝.  boolean[]不能代替set的剪枝功能,因为boolean是有一个default=false的值的,只能够标示在i这里是可以wordbreak的.而剪枝需要标示:在这里是不能够wordbreak从而减少iteration.(04/23)

所以其实可以用一个int[] array, default = 0表示没有visited, -1表示当前index不能break,1表示可以. (09/17)

然后string操作可以用s.indexOf(w, index)或者s.startsWith(w, index)

  • 剪枝:用一个Set<Integer>来存从charAt index这个char之前切一刀的话,剩下的一整个substring是不能够workbreak的/该charAt index开始到词末是不能够进行word break的,
  • dfs传入string,dict,memorizing set和一个int index,返回boolean表示:从charAt index这里开始到string的最后是否能够word break。同时也表示index之前的substring是能够wordbreak的。
    • 如果index == str.length():抵达词末,表示前面的均可work break,返回true。
    • 如果index存在于set中:表示从这里到最后是不能够work break的,直接返回false。
    • 否则 for loop开始切substring:i从index+1到词末,substring从index到i切。如果substring不存在wordDict中,continue;如果存在,那么继续if(dfs传入i) 中进行dfs,下一轮的dfs就是从index=i开始往后找存在于dict中的substring,所以切割字符串的起点在不断往后推。(所以当找到最后index==str.length的时候代表之前的均可wordbreak,所以返回true)如果这个dfs最终为true的话,返回true。
    • 整个for loop循环之后如果没有返回true的话,说明从index到最后的substring是不能够word break的,于是在set里面加入index。并且返回false。
public boolean wordBreak(String s, Set wordDict) {
 Set<Integer> cantBreak = new HashSet<>();
 return helper(s, wordDict, cantBreak, 0);
 }
 
 private boolean helper(String s, Set<Integer> wordDict, 
 Set<Integer> cantBreak, int curIndex){
 if (curIndex == s.length()) return true;
 if (cantBreak.contains(curIndex)) return false;//剪枝
 //因为substr要从curIndex开始切
 for (int i = curIndex + 1; i <= s.length(); i ++){
 String subStr = s.substring(start, i);
 if (wordDict.contains(subStr) && helper(s, wordDict, cantBreak, i))
 return true;
 }
 cantBreak.add(curIndex);//加入set
 return false;
 }

四、BFS:用了图论的方法。

图:a->b表示str.substring(a, b)存在于dict中。例子:

  • dict:[night, mare, nightmare];word:nightmare
    • 图有两种:0->5->9和0->9,代表有两种word break的方式
  • dict:[leet, code]; word:leetcode
    • 图有一种:0->4->8,代表有一种wordbreak的方式

所以最后变成了从0-str.length()是否存在一条通路。

用一个visited set来消除重复访问:当加入queue的时候,同时也加入visited,说明在index这里已经有一种切分方法满足word break条件了,所以不论下一次的index为什么,遇到i==visited的时候都没有必要再substring进行判断了。直接跳过。这里极大的减少了时间复杂度。

 public boolean wordBreak(String s, Set dict) {
    if (dict.contains(s)) return true;
    Queue queue = new LinkedList();
    queue.offer(0);
    // use a set to record checked index to avoid repeated work.
    // This is the key to reduce the running time to O(N^2).
    Set visited = new HashSet<>();
    visited.add(0);
    while (!queue.isEmpty()) {
        int curIdx = queue.poll();
        for (int i = curIdx+1; i <= s.length(); i++) {
            if (visited.contains(i)) continue;
            if (dict.contains(s.substring(curIdx, i))) {
                if (i == s.length()) return true;
                queue.offer(i);
                visited.add(i);
            }
        }
    }
    return false;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: