Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].

A solution is [“cats and dog”, “cat sand dog”].

碰到一个求所有解的问题,首先就想到recursive的方法,backtracking。但是太慢,无法通过OJ

public class Solution {
    public ArrayList wordBreak(String s, Set dict) {
        ArrayList result = new ArrayList();
        if (s.length() == 0)
            return null;
        if (dict.size() == 0)
            return null;
        for (int i = 0; i < s.length(); i++)
        {
            if(dict.contains(s.substring(0, i)))
            {
                for (String t : wordBreak(s.substring(i, s.length()), dict))
                {
                    String temp = s.substring(0, i) + " " + t;
                    result.add(temp);
                }
            }
        }
        if (dict.contains(s))
        {
            result.add(s);
        }
        return result;
    }
}

于是想到用WordBreak I的方法,但是DP只能求出是否存在解(每个dp[i]记录是否可以分割(0:i))但是没法输出解。
于是再用backtracking recursive的方法来找出解,这时候我们只需要check dp[i] == true的位置即可。
具体步骤
1. 用WordBreakI的方法算出dp[i],每个dp[i]==true表示(0:i)这个substring可以分割。
2. 从后往前向前scan整个string,如果dp[i]是false的话,直接跳过
3. 如果dp[i]==true的话,首先check(0:i)是否在dict里面,如果是,加入,然后再recursive的check所有的substring,也是只check dp[i]=true的地方。
4. 最后return结果即可。

//use dp to calculate solution and use backtracking to recover result;
public class Solution {
    boolean [] dp;
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> result = new ArrayList<String>();
        getPossiblePosition(s, dict);
        if (dp[s.length()] == false)
            return result;
        return wordBreakWithIndex(s, dict, s.length());
    }
    
    public ArrayList<String> wordBreakWithIndex(String s, Set<String> dict, int start) // go from s.length to 0 more effienient.
    {
        ArrayList<String> result = new ArrayList<String>();
        if (s.length() == 0)
            return result;
        if (dict.size() == 0)
            return result;
        if (dict.contains(s))// first check the full string.
            result.add(s);
        for (int i = s.length()-1; i > 0; i--)//then check substring
        {
            if (dp[i] == true)
            {
                if (dict.contains(s.substring(i, s.length())))
                {
                    for (String t : wordBreakWithIndex(s.substring(0, i), dict, i))
                    {
                        String temp = t + " " + s.substring(i, s.length());
                        result.add(temp);
                    }
                }
            }
        }
        return result;
    }
    
    public void getPossiblePosition(String s, Set<String> dict)
    {
        dp = new boolean [s.length() + 1]; 
        if (s.length() == 0)
            return;
        if (dict.size() == 0)
            return;
        dp[0]= true;
        for (int i = 1; i <= s.length(); i++)
        {
            if (dict.contains(s.substring(0, i)) || dp[i] == true)
            {
                dp[i] = true;
                for(String word : dict)
                {
                    if (i+word.length() > s.length())
                        continue;
                    if (s.substring(i, i+word.length()).equals(word))
                        dp[i+word.length()] = true;
                }
            }
        }
    }
}

第二次提交,总结一下,用word break I的办法找到dp,然后在dfs递归的时候,如果dp是true的才进去字典查找。

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        boolean [] dp = new boolean [s.length()+1]; // if string before this char (exclusive) can be seperated in to words in dictionary
        if (getDP(s, dict, dp))
            return getResult(s, dict, dp, s.length());
        return new ArrayList<String>();
    }

    public boolean getDP(String s, Set<String> dict, boolean[] dp) {
        dp[0] = true; //test substring(0, i) first
        int curr = 0;
        while(curr < s.length()) {
            if (dp[curr])
                for(String st : dict) {
                    if (st.length() + curr <= s.length() && st.equals(s.substring(curr, curr + st.length()))) {
                        dp[curr + st.length()] = true;
                    }
                }
            curr++;
        }
        return dp[s.length()];
    }
    
    public ArrayList<String> getResult(String s, Set<String> dict, boolean[] dp, int end) {// dfs get result from the dp array
        ArrayList<String> result = new ArrayList<String>();
        if (end == 0)
            return result;
        for (int i = end; i >= 0; i--) {
            if (dp[i]) {
                for (String t : dict) {
                    if (t.equals(s.substring(i, end))) {
                        ArrayList<String> temp = getResult(s, dict, dp, i);
                        if (temp.isEmpty())
                            result.add(t);
                        else {
                            for (String tempS : temp) {
                                result.add(tempS + " " + t);
                            }
                        }
                        break;// if find one, no need to keep searching
                    }
                }
            }
        }
        return result;
    }    
}

Simpler code, first get the dp, then only recursive call when you have true in the dp array.

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        boolean [] dp = new boolean [s.length()]; //first we calculate which words can be seperated to speed up recursive calculation
        for (int i = 0; i < s.length(); i++) {
            if (dict.contains(s.substring(0, i+1)))
                dp[i] = true;
            else {
                for (int j = 0; j < i; j++) {
                    if (dict.contains(s.substring(j+1, i+1)) && dp[j] == true) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return getWords(s.length()-1, s, dp, dict);
    }
    
    public ArrayList<String> getWords(int end, String s, boolean [] dp, Set<String> dict) {
        ArrayList<String> res = new ArrayList<String>();
        if (dict.contains(s.substring(0, end+1))) {
            res.add(s.substring(0, end+1));
        }
        for (int i = end-1; i >= 0; i--) {
            if (dp[i] == true && dict.contains(s.substring(i+1, end+1))) {
                ArrayList<String> r = getWords(i, s, dp, dict);
                for (String str : r) {
                    res.add(str + " " + s.substring(i+1, end+1));
                }
            }
        }
        return res;
    }
}

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