Word Break

题目
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. You may assume the dictionary does not contain duplicate words.

For example, given

s = "leetcode",
dict = ["leet", "code"].

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

分析
第一眼看到这个题目，或许最直觉的方法就是，把s分成若干份，这样有很多种分法，对每一种分法，检查每一份word是否在word list里。

但是这样显然特别慢,可以有(n choose 1) + (n choose 2) + ... (n choose n)种分法。
下面用dp思路解决这个问题
定义dp[i] = true when s[i...n] has a word break, false otherwise
base case是dp[i] = whether s[i...n] is in word list, for all i

s: |____________|_______|
1........................k.............n

假设我们已经知道了dp[k+1...n], dp[k+2, ...n], ... dp[n]，那么如何知道[k...n]之间是否有word break?

for i = k to n
  dp[k] = true if s[k...i] is a word in word list and dp[i+1] is true

如果从index k到i之间的string在word list里面，而且我们已经知道从index i+1 到n之间的string有word break，那么就可以确定s[k...n]之间是否有word break了。

因为basecase是dp[n], 有了dp[n]可以计算dp[n-1], dp[n-2], 进而计算出dp[1]。也就是可以计算出s[1...n]之间是否有word break。

以上的解释是以string的index是从1开始算的，代码里是以0开始，请注意区分一下

public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        HashMap<String, Boolean> wordMap = new HashMap<String, Boolean>();

        // Put each word into wordMap for quick lookup
        for(String word : wordDict) {
            wordMap.put(word, true);
        }
        // dp array
        boolean[] hasWordBreak = new boolean[n+1];

        // Does string from index n-1 (to n-1) have a word break?
        for(int i = n-1; i >= 0; i--) {
            String curr_word = s.substring(i, n);
            hasWordBreak[i] = wordMap.get(curr_word) != null;
        }

        hasWordBreak[n] = false;

        for(int k = n-1; k >= 0; k--) {
            for(int i = k; i < n; i++) {
                String curr_word = s.substring(k, i + 1);
                if(wordMap.get(curr_word) != null && hasWordBreak[i + 1]) {
                    hasWordBreak[k] = true;
                    break;
                }

            }
        }

        return hasWordBreak[0];
    }

时间复杂度为O(n^2), 因为主要的计算发生在一个二维循环里
这道题如果用常规的方法来做肯定会超时

回头看看这篇文章如何解这道题
http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/