624.移除子串

描述

给出一个字符串 s 以及 n 个子串。你可以从字符串 s 中移除 n 个子串中的任意一个，使得剩下来 s 的长度最小，输出这个最小长度。

样例

给出 s = ccdaabcdbb，子串为 ["ab","cd"]
返回 2.

解释

ccdaabcdbb -> ccdacdbb -> cabb -> cb (长度为 2)

知识点

思路

解法是 BFS，扩展出能够通过删子串得到的所有字符串，然后选出最短的
删除子串的方式并不是想的那种连续删除一个子串多次，而是这次通过查找子串1出现的不同位置删除子串 1得到多个新的字符串，将所有得到的新的字符串加入队列，进入下一轮删除，后续删除的子串可能和之前删除的子串 1是同一子串，仔细看样例，有时候连续删除并不可行
每一层 bfs 在抛出字符串的不同位置移除字典中的某一子串一次，需要强调，只移除某一子串，且只操作一次

代码

public class Solution {
    /**
     * @param s a string
     * @param dict a set of n substrings
     * @return the minimum length
     */
    public int minLength(String s, Set<String> dict) {
        Queue<String> queue = new LinkedList<String>();
        Set<String> hash = new HashSet<String>();
    
        int min = s.length();
        queue.offer(s);
        hash.add(s);

        while (!queue.isEmpty()) {
            String string = queue.poll();
            for (String sub : dict) {
                /* 字符串的 IndexOf() 方法
                 * 搜索在该字符串上是否出现了作为参数传递的字符串,
                 * 如果找到字符串,则返回字符的起始位置 
                 * (0表示第一个字符,1表示第二个字符依此类推)
                 * 如果说没有找到则返回 -1 
                 */
                int found = string.indexOf(sub);
                while (found != -1) {
                    // 即使字符串中有多个 sub 每次也只截掉一个
                    // new_s 为截掉 sub 后新的字符串
                    String new_s = string.substring(0, found) +
                        string.substring(found + sub.length(), string.length());
                    /* 当找到一个子串的时候，可能 string 中有多个这样的子串， 
                     * 并不是只在子串出现的第一个位置删除，
                     * 而是在所有可以删除这个子串的位置都删除一遍，
                     * 字符串 string 在不同位置删除子串会得到得到不同的的字符串
                     * 此处不是连续删除一个子串多次，
                     * 而是在不同位置删除一次得到多个子串
                     * 通过 while 循环在不同位置删除子串
                     * 通过 for 循环进行多次删除每个子串
                     * 在最终得到的所有字符串中选最短的
                     */
                    // 检查得到的字符串之前有没有出现过
                    if (!hash.contains(new_s)) {
                        // 这句要写在hash表判断之后
                        if (new_s.length() < min) {
                            min = new_s.length();
                        }
                        queue.offer(new_s);
                        hash.add(new_s);
                    }
                    /* 从 found + 1 开始搜索子串下一个出现的位置，如果找不到返回-1
                     * 尝试在 string 的不同位置删除同一子串，得到多种不同的结果，
                     * 加入队列然后抛出，对 dict 中子串(可以和上一次删除的子串
                     * 相同)进行下一次删除
                     */
                    found = string.indexOf(sub, found + 1);
                }
            }
        }
        return min;
    }
}