LeetCode-Word Break

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

一看這題目，就感覺裡面回溯法，因為這種題，在回溯法中在平常不過了。上代碼：

public boolean wordBreak(String s, Set dict) {
    	StringBuilder sb = new StringBuilder();
        return helper(s, dict, 0, sb);
    }
    private boolean helper(String s, Set dict, int index, StringBuilder sb) {
    	if (index == dict.size()) {
    		return s.equals(sb.toString());
    	}
    	Iterator iter = dict.iterator();
    	while (iter.hasNext()) {
    		StringBuilder sb1 = new StringBuilder(sb);
    		String dic = iter.next();
    		sb.append(dic);
    		iter.remove();
    		if (helper(s, dict, index+1, sb))
    			return true;
    		dict.add(dic);
    		sb = sb1;
    	}
    	return false;
    }

結果超時！一般情況下，對於回溯的時間限制都是比較寬的，但是超時！肯定有優化的空間吧，剪枝啊：、

public boolean wordBreak(String s, Set dict) {
    	StringBuilder sb = new StringBuilder();
        return helper(s, dict, 0, sb);
    }
    private boolean helper(String s, Set dict, int index, StringBuilder sb) {
    	if (!s.startsWith(sb.toString())) {
    		return false;
    	}
    	if (index == dict.size()) {
    		return s.equals(sb.toString());
    	}
    	Iterator iter = dict.iterator();
    	while (iter.hasNext()) {
    		StringBuilder sb1 = new StringBuilder(sb);
    		String dic = iter.next();
    		sb.append(dic);
    		iter.remove();
    		if (helper(s, dict, index+1, sb))
    			return true;
    		dict.add(dic);
    		sb = sb1;
    	}
    	return false;
    }

其實這個剪枝可以減去很多分支，但是還是超時！怎麼辦？只能用最高效的動態規劃了，上代碼：

public boolean wordBreak1(String s, Set dict) {
    	int length = s.length();
        boolean[] can = new boolean[length+1];
        can[0] = true;
        for (int i = 1; i <= length; i++) {
            for (int j = 0; j < i; j++) {
                if (can[j] && dict.contains(s.substring(j, i))) {
                    can[i] = true;
                    break;
                }
            }
        }
        return can[length];
    }

boolean數組can[i]是指，s.substring(0,i)是可以分割的，所示數組最後一個元素即為所求。