字符串按词典分割

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

思路：

可以考虑用动态规划，用f(i,j)表示字符串S从i到j的子串是否可分割，则有：f(0,n) = f(0,i) && f(i,n)，然后f(0,i)和f(i,n)又可以继续分割。

	public boolean wordBreak(String s, Set
  
    dict) 
	{
		if(dict.size()==0)
			return false;
		if(s.equals("")||s==null)
			return true;
		ArrayList
   
     list = new ArrayList
    
     ();//存放能够被检索的字符串的位置 int len = s.length(); String str,strtemp; for(int i = len-1;i>=0;i--) { str = s.substring(i); if(dict.contains(str)) { list.add(i); } else { //如果词典中不包含的话就在已经分割的字符串中找，比如字符串是“hello”，而词典中有“hel”和“lo”,那么就先匹配“lo”，再匹配“hel” for(Integer index : list) { strtemp = s.substring(i, index); if(dict.contains(strtemp)) { list.add(i); break; } } } } if(list.size()>0&&list.get(list.size()-1)==0) return true; else return false; }