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

解题思路一：

直接暴力枚举会导致TLE，因此，需要记录之前的结果，即可以采用dp的思路，JAVA实现如下：

static public boolean wordBreak(String s, Set
     
       wordDict) {		boolean[] dp = new boolean[s.length() + 1];		dp[0] = true;		for (int i = 1; i < dp.length; i++)			for (int j = i; j >= 0 && !dp[i]; j--)				if (wordDict.contains(s.substring(i - j, i)))					dp[i] = dp[i - j];		return dp[dp.length - 1];	}
     

 解题思路二：

考虑到下题用dp做不出来，暴力枚举肯定TLE，所以可以设置一个unmatch集合来存储s中已经确定无法匹配的子串，从而避免重复检查，JAVA实现如下：

static public boolean wordBreak(String s, Set
     
       dict) {		return wordBreak(s, dict, new HashSet
      
       ());	}	static public boolean wordBreak(String s, Set
       
         dict,			Set
        
          unmatch) {		for (String prefix : dict) {			if (s.equals(prefix))				return true;			else if (s.startsWith(prefix)) {				String suffix = s.substring(prefix.length());				if (!unmatch.contains(suffix)) {					if (wordBreak(suffix, dict, unmatch))						return true;					else						unmatch.add(suffix);				}			}		}		return false;	}