题目

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

方法

与http://blog.csdn.net/u010378705/article/details/28304963思想一样。

但是需要判断是不是可以分割的，针对的是“aaaaaaaaaaaaaaaaaab”这种情况

public class LeetCode {
	  public boolean isWordBreak(String s, Set<String> dict) {
		  
		  if (s == null) {
			  return false;
		  } else if (s.length() == 0){
			  return false;
		  } else if (s.length() == 1) {
			  if (dict.contains(s)) {
				  return true;
			  } else {
				  return false;
			  }
		  } else {
			  int len = s.length();
			  
			  int maxLen = 0;
			  int minLen = 100;
			  for (String str: dict) {
			  	if (str.length() > maxLen) {
			  		maxLen = str.length();
			  	} 
			  	if (str.length() < minLen) {
			  		minLen = str.length();
			  	}
			  }
			  boolean[] status = new boolean[len + 1];
			  status[len] = true;
			  
			  for (int i = len - 1; i >= 0; i--) {
				  for (int j = i + minLen ; j <= Math.min(len, maxLen + i); j++) {
					  String subStr = s.substring(i, j);
					  if (dict.contains(subStr) && status[j]) {
						  status[i] = true;
						  break;
					  }
					  status[i] = false;
				  }
			  }
			  return status[0];
		  }	  
	}
	private void  dictArray(String s, Set<String> dict, boolean[][] status) {
		int len = s.length();
		for (int i = 0; i < len; i++) {
			for (int j = i; j  < len; j++) {
				String str = s.substring(i, j + 1);
				if (dict.contains(str)) {
					status[i][j] = true;
				}
			}
		}
	}
	
	public void getList(String s, int start, boolean[][] status, List<String> list, String str) {
		int len = s.length();
		if (start == len) {
			list.add(str.substring(0,str.length() - 1));
			return;
		} else {
			for (int i = start; i < len; i++) {
				if (status[start][i] == true) {
					StringBuilder builder = new StringBuilder(str);
					builder.append(s.subSequence(start, i + 1) + " ");
					String temp = builder.toString();
					getList(s, i + 1, status, list, temp);
				}
			}
			
		}
	}
	
    public List<String> wordBreak(String s, Set<String> dict) {
    	if (s == null) {
    		return null;
    	} else if (s.length() == 0){
    		return null;
    	} else {
    		List<String> list = new ArrayList<String>();
    		
    		if (s.length() == 1) {
    			if (dict.contains(s)) {
    				list.add(s);
    			}
    			return list;
    		} else {   	
    			if (this.isWordBreak(s, dict)){
        	    	int len = s.length();
        	    	boolean[][] status = new boolean[len][len];
        	    	dictArray(s, dict, status);
        	    	String str = "";
        	    	getList(s, 0, status, list, str);
    			}
    	    	return list;
    		}
    	}	
    }
	public static void main(String[] args) {
		String[] dicto = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
		Set<String> dict = new HashSet<String>(Arrays.asList(dicto));
		String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
		List<String> list = new LeetCode().wordBreak(s, dict);
		for (String str: list) {
			System.out.println(str);
		}
	}

}