Word Break

描述

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)，表示s[0,i)是否可以分词，则状态转移方程为

f(i) = any_of(f(j) && s[j,i] in dict), 0 <= j < i

深搜

  1. // Word Break
  2. // 深搜，超时
  3. // 时间复杂度O(2^n)，空间复杂度O(n)
  4. class Solution {
  5.     public boolean wordBreak(String s, Set<String> dict) {
  6.         return dfs(s, dict, 0, 1);
  7.     }
  8.     private static boolean dfs(String s, Set<String> dict,
  9.                     int start, int cur) {
  10.         if (cur == s.length()) {
  11.             return dict.contains(s.substring(start, cur));
  12.         }
  13.         if (dfs(s, dict, start, cur+1)) return true; // no cut
  14.         if (dict.contains(s.substring(start, cur))) // cut here
  15.             if (dfs(s, dict, cur+1, cur+1)) return true;
  16.         return false;
  17.     }
  18. }

动规

  1. // Word Break
  2. // 动规，时间复杂度O(n^2)，空间复杂度O(n)
  3. class Solution {
  4.     public boolean wordBreak(String s, Set<String> dict) {
  5.         // 长度为n的字符串有n+1个隔板
  6.         boolean[] f = new boolean[s.length() + 1];
  7.         f[0] = true; // 空字符串
  8.         for (int i = 1; i <= s.length(); ++i) {
  9.             for (int j = i - 1; j >= 0; --j) {
  10.                 if (f[j] && dict.contains(s.substring(j, i))) {
  11.                     f[i] = true;
  12.                     break;
  13.                 }
  14.             }
  15.         }
  16.         return f[s.length()];
  17.     }
  18. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dp/word-break.html