**[Lintcode]Word Break单词切分

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

分析：Brute force。超时

public class Solution { /** * @param s: A string s * @param dict: A dictionary of words dict */ public boolean wordBreak(String s, Set<String> dict) { if(s == null || s.length() == 0) return true; for(int i = 0; i < s.length(); i++) { if(dict.contains(s.substring(0, i + 1)) && wordBreak(s.substring(i + 1), dict)) return true; } return false; } } 二维动态规划：res[i][j]代表从i到j的子字符串是否可以匹配。仍然超时

public class Solution { /** * @param s: A string s * @param dict: A dictionary of words dict */ public boolean wordBreak(String s, Set<String> dict) { if(s == null || s.length() == 0) return true; boolean[][] res = new boolean[s.length()][s.length()]; if(dict.contains(s)) return true; for(int i = 0; i < s.length(); i++) { res[0][i] = dict.contains(s.substring(0, i + 1)) ? true : false; } for(int i = 0; i < s.length(); i++) { for(int j = i; j < s.length(); j++) { if(i == j && dict.contains(s.substring(i, i + 1))) { res[i][j] = true; continue; } for(int k = i; k <= j; k++) { String tmp1 = s.substring(i, k + 1); String tmp2 = s.substring(k + 1, j + 1); if(k + 1 < s.length()) { res[i][j] |= (res[i][k] || dict.contains(tmp1)) && (res[k + 1][j] || dict.contains(tmp2)); } else { res[i][j] |= (res[i][k] || dict.contains(tmp1)); } if(res[i][j]) break; } } } return res[0][s.length() - 1]; } }

继续改进，使用一维动态规划。res[i]代表0到i的子字符串是否可以完成单词切分。一般动态规划是从i到i-1进行分析，但是这里要换一个角度，在i时，考虑i后边的i+k位置，k为每一个字符串可能的长度。

public class Solution { /** * @param s: A string s * @param dict: A dictionary of words dict */ public boolean wordBreak(String s, Set<String> dict) { if(s == null || s.length() == 0) return true; boolean[] res = new boolean[s.length() + 1]; res[0] = true; for(int i = 0; i < s.length(); i++) { if(!res[i]) continue; else { for(String str : dict) { int end = i + str.length(); if(end > s.length()) continue; if(s.substring(i, end).equals(str)) res[end] = true; } } } return res[s.length()]; } }