30. Substring with Concatenation of All Words

字符串的模式匹配一直是个很经典的问题，能写好几本书。单模式匹配有KMP/BM算法，多模式匹配有AC/WM算法等等，还有各种适用于特殊场景的算法，可以说已经被玩坏了。。。

我只稍微看过一点BM算法，很简单很优雅。其他的算法还有点复杂的。

刚看到这道题目的时候，第一感觉就是多模式匹配。给定一堆pattern，在字符串s中搜索。于是去google AC算法了，看得头晕。后来想想不对啊，这个pattern是有规律的，比如所有pattern长度是相同的，所有出现的字符也都是固定的，也许不必用那么复杂的算法。杀鸡焉用牛刀。

模式匹配算法的关键就是减少比较次数。最笨的办法就是index从0开始，依次去搜索是否符合某个pattern，然后index++，继续重复搜索。伪代码：

for (int i = 0; i < s.length(); i++) {
    for (String p : patterns) {
        if (s.substring(i).startsWith(p)) {
            // 把i加到结果List里
        }
    }
}

在此基础上，应该如何减少比较次数？我采用了几个策略：

• pattern长度是固定的，所以当s“剩余”的长度小于pattern长度时，就不用再比较了。这个是比较容易想到的。
• 借鉴BM算法的“坏字符”策略。如果char[i]不是任何pattern中的字符，直接跳到i+1。另外还借鉴了BM算法一点：从pattern尾部开始比较，而不是头部。
• pattern是由长度相同的几个词排列而成。在从char[i]开始比较时，我们应该可以“预测”到char[i+1]是什么。比如输入的words是["ab","cd"]，当前字符是a，那么下一个字符必须是b。如果是c或d，就直接break，后面都不用再比较了。我会为可能的pattern建一个“索引”，以快速判断是否跳过。

这也是比较常见的解题思路了。先给出一个最笨的解法，然后在这个基础上去优化。很多问题都可以这样。当然也有些问题从开始就会用一个完全不同的思路，不能一概而论。

我的解法：

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<Integer>();
        if (s == null || words == null)
            return result;

        int wordCount = words.length;
        int lenPerWord = words[0].length();
        if (wordCount == 0 || s.length() < wordCount * lenPerWord)  // 这个边界条件还是比较容易想到的
            return result;

        // 存储pattrn中出现过的所有字符
        Set<Character> goodChars = new HashSet<Character>();
        CharNode dummy = new CharNode();
        dummy.c = 'x';

        // 准备工作：建索引，顺便更新goodChars
        // 这个索引的结构可能比较难理解，我关注的是一个字符的下一个字符可能是什么
        // 比如输入是["ab","cd"]，建好的索引就是dummy->a->b，dummy->c->d
        // 代表第一个字符可能是a或c，如果第一个字符是a，那么下一个字符必须是b；如果第一个字符是c，下一个字符必须是d
        // 因为可能有重复的输入，比如["ab","ab"]，所以还要用一个count表示某个word出现了几次
        // 换句话说，在匹配的时候，某个word可以被“使用”几次
        for (int j = 0; j < words.length; j++) {
            CharNode current = dummy;
            for (int i = 0; i < words[j].length(); i++) {
                char thisChar = words[j].charAt(i);
                goodChars.add(thisChar);
                if (!current.next.containsKey(thisChar)) {
                    CharNode tmp = new CharNode();
                    tmp.c = thisChar;
                    current.next.put(thisChar, tmp);
                    current = tmp;
                } else {
                    current = current.next.get(thisChar);
                }
            }
            current.count++;
        }
        //System.out.println(dummy);

        // 准备工作结束，正式开始匹配
        int lastEnd = 0;
        // 注意i的终止条件。另外i不要在for语句里更新。
        for (int i = 0; i <= s.length() - wordCount * lenPerWord;) {
            // begin和end都是inclusive
            int begin = i, end = i + wordCount * lenPerWord - 1;
            // bad chars
            int badChar = -1;
            // 从尾部开始找bacChar，这里用j>=lastEnd是为了减少匹配次数，如果用j>=begin也可以，但效率会低一些
            // begin到lastEnd之间的字符，都是在上次for循环里匹配过的
            for (int j = end; j >= lastEnd; j--) {
                if (!goodChars.contains(s.charAt(j))) {
                    badChar = j;
                    break;
                }
            }
            lastEnd = end + 1;
            // 如果找到了bacChar，直接跳到下一个位置，开始下次比较
            if (badChar != -1) {
                i = badChar + 1;
                continue;
            }
            // 如果没有找到badChar，就判断[begin,end]这段substring，是否符合某个pattern，这时就用到索引了
            if (validateSubstr(dummy, s, begin, end, lenPerWord, wordCount)) {
                result.add(begin);
            }
            // 只有找到bacChar时i能跳的很快，否则只能老老实实i++
            i++;
        }

        return result;
    }

    // 校验字符串s从begin到end这段substring，是否符合某个pattern
    // 包括begin和end
    private boolean validateSubstr(CharNode root, String s, int begin, int end, int lenPerWord, int wordCount) {
        // 在校验过程中，我们要做一些count--的操作，事后必须把这些count再加回来
        List<CharNode> minusOne = new ArrayList<CharNode>();
        boolean result = true;
        // 还是要理解索引的结构，不然下面这段代码不太好理解
        // 比如输入是["abc","def"]，我会从begin开始找第一个word，就是前3个字符
        // 如果是"abd"，虽然a/b/d都是goodChar，但b后面不可能是d，匹配失败
        // 如果是"abc"，那么我就认为"abc"已经出现过了，对应的count--，变成0，继续找第二个word，也就是第4到6个字符
        // 如果第二个word还是"abc"，虽然符合索引，能找到对应的count，但count已经是0了，说明"abc"已经被“用光”了，匹配失败
        for (int i = 0; i < wordCount; i++) {
            CharNode current = root;   // 开始匹配一个word的过程
            for (int j = 0; j < lenPerWord; j++) {
                char thisChar = s.charAt(begin + i * lenPerWord + j);
                // 不符合索引，直接失败
                if (!current.next.containsKey(thisChar)) {
                    result = false;
                    break;
                }
                current = current.next.get(thisChar);
            }
            // 一个经典问题：如何跳出两层for循环
            if (!result)
                break;
            // 如果当前word已经没有“富余”了，匹配失败
            if (current.count <= 0) {
                result = false;
                break;
            }
            // 某个word被使用一次
            current.count--;
            minusOne.add(current);
        }
        // 最后别忘了加回来
        for (CharNode node : minusOne) {
            node.count++;
        }

        return result;
    }
}

// 这是一个辅助类，充当索引
class CharNode {
    char c;  // 当前字符
    int count = 0;  // 其实只有每个word结尾那个字符的count有用 
    Map<Character, CharNode> next = new HashMap<Character, CharNode>();  // 当前字符的下一个字符可能是什么？

    // 以下两个方法是用于debug的
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (String s : innerToString()) {
            sb.append(s);
            sb.append("\n");
        }
        return sb.toString();
    }

    private List<String> innerToString() {
        List<String> res = new ArrayList<String>();
        if (next.size() != 0) {
            for (CharNode tmp : next.values()) {
                for (String s : tmp.innerToString()) {
                    res.add(this.c + "->" + s);
                }
            }
        } else {
            res.add(this.c + ":" + count);
        }
        return res;
    }
}

我发现要解释清楚我的思路还是有点难的。。。其实我写代码的时候就很心虚，感觉我的思路有点偏，难道是脑洞太大。。。而且代码也有点长，纯算法题写太长的代码，总觉得有问题。提交的时候已经做好出错的心理准备了，结果一次就AC，还能beat 41.6% java submissions，心满意足了。。。

另外我发现我的代码工程化风格很明显啊。。。各种辅助类、辅助方法，还有变量名，方法名之类的，讲究可读性。还有“建索引”的这种想法，也是工作中常用到的。最关键的是，长。。。看了一些其他人的解法，确实简短高效，但我就是想吐槽l/r/m/k之类的变量名。。。我始终觉得，代码清晰是最重要的，不能盲目追求简短或者追求效率。