P98 字符串分解

描述#

这个题目说的是，给你一个非空字符串，和一个非空的字符串列表。你是否可以把这个字符串分解成若干个子串，这些子串都存在于给你的字符串列表中。

比如说给你的字符串是：
carandcard
给你的字符串列表是：
car, rand, and, d
carandcard 可以被分解成 4 个部分：car, and, car 和 d，这些子串都存在于字符串列表中。因此，你要返回 true。
如果给你的字符串仍然是 carandcard，但给你的字符串列表是：
car, rand, card
原字符串就无法找到一种分解，使得分解后的子串都存在于给你的字符串列表中。于是你要返回 false。

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(n+m)
  public boolean stringBreak(String s, List<String> list) {
    int n = s.length();
    boolean[] d = new boolean[n+1];
    d[0] = true;
    Set<String> set = new HashSet<>(list);
    for (int i = 1; i <= n; ++i) {
      for (int j = i-1; j >= 0; --j) {
        if (d[j] && set.contains(s.substring(j, i))) {
          d[i] = true;
          break;
        }
      }
    }
    return d[n];
  }

}