一、问题描述

给定一个字符串 source 和一个单词字典，确定 source 是否可以被字典分解为多个单词。如：
给定字符串：source=“HelloWorld”。单词字典：dict=[“Hello”,“World”]。由于“HelloWorld”可被分割为“Hello”,“World”，所以返回 true。

二、解法一

遍历 dict 中的单词，查看其是否在 source 的起始位置，若在则继续查看 source 剩下的部分，否则返回 false。

public static boolean wordBreak(String source, Set<String> dict, int start) {
    if (start == source.length())
        return true;
    for (String a : dict) {
        int len = a.length();
        int end = len + start;
        //长度大于source，说明不可能是dict中的这个单词，遍历尝试dict中下一个单词
        if (end > source.length())
            continue;

        if (source.substring(start, end).equals(a))
            if (wordBreak(source, dict, end))
                return true;
    }
    return false;
}

三、解法二

利用一个长度为source.length+1的 boolean 型数组 t，初始化时将 t[0] 设为 true，其它设为 false。t[i] == true表示0~(i-1)可被分割，最后可以通过查看t[s.length()]的值判断 source 是否能被 dict 分割。

public static boolean wordBreak(String s, Set<String> dict) {
    boolean[] t = new boolean[s.length() + 1];
    t[0] = true;

    for (int i = 0; i < s.length(); i++) {
        if (!t[i])
            continue;

        for (String a : dict) {
            int len = a.length();
            int end = i + len;
            if (end > s.length())
                continue;

            if (t[end]) continue;

            if (s.substring(i, end).equals(a)) {
                t[end] = true;
            }
        }
    }
    return t[s.length()];
}

四、解法三

使用正则表达式

public static void breakWord(HashSet<String> dict) {
    StringBuilder sb = new StringBuilder();
    for (String s : dict) {
        sb.append(s + "|");
    }
    String pattern = sb.substring(0, sb.length() - 1);
    pattern = "(" + pattern + ")*";
    Pattern p = Pattern.compile(pattern);
    Matcher m = p.matcher("HelloWorld");

    if (m.matches()) {
        System.out.println("match");
    }
}

五、测试主类

public static void main(String[] args) {
    String source = "HelloWorld";
    Set<String> dict = new HashSet<>();
    dict.add("Hello");
    dict.add("World");
    System.out.println(wordBreak(source, dict, 0));
}