描述

給出一個(gè)字符串 s 以及 n 個(gè)子串。你可以從字符串 s 中移除 n 個(gè)子串中的任意一個(gè)，使得剩下來 s 的長度最小，輸出這個(gè)最小長度。

樣例

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

解釋

ccdaabcdbb -> ccdacdbb -> cabb -> cb (長度為 2)

知識(shí)點(diǎn)

思路

解法是 BFS，擴(kuò)展出能夠通過刪子串得到的所有字符串，然后選出最短的
刪除子串的方式并不是想的那種連續(xù)刪除一個(gè)子串多次，而是這次通過查找子串1出現(xiàn)的不同位置刪除子串 1得到多個(gè)新的字符串，將所有得到的新的字符串加入隊(duì)列，進(jìn)入下一輪刪除，后續(xù)刪除的子串可能和之前刪除的子串 1是同一子串，仔細(xì)看樣例，有時(shí)候連續(xù)刪除并不可行
每一層 bfs 在拋出字符串的不同位置移除字典中的某一子串一次，需要強(qiáng)調(diào)，只移除某一子串，且只操作一次

代碼

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() 方法
                 * 搜索在該字符串上是否出現(xiàn)了作為參數(shù)傳遞的字符串,
                 * 如果找到字符串,則返回字符的起始位置 
                 * (0表示第一個(gè)字符,1表示第二個(gè)字符依此類推)
                 * 如果說沒有找到則返回 -1 
                 */
                int found = string.indexOf(sub);
                while (found != -1) {
                    // 即使字符串中有多個(gè) sub 每次也只截掉一個(gè)
                    // new_s 為截掉 sub 后新的字符串
                    String new_s = string.substring(0, found) +
                        string.substring(found + sub.length(), string.length());
                    /* 當(dāng)找到一個(gè)子串的時(shí)候，可能 string 中有多個(gè)這樣的子串， 
                     * 并不是只在子串出現(xiàn)的第一個(gè)位置刪除，
                     * 而是在所有可以刪除這個(gè)子串的位置都刪除一遍，
                     * 字符串 string 在不同位置刪除子串會(huì)得到得到不同的的字符串
                     * 此處不是連續(xù)刪除一個(gè)子串多次，
                     * 而是在不同位置刪除一次得到多個(gè)子串
                     * 通過 while 循環(huán)在不同位置刪除子串
                     * 通過 for 循環(huán)進(jìn)行多次刪除每個(gè)子串
                     * 在最終得到的所有字符串中選最短的
                     */
                    // 檢查得到的字符串之前有沒有出現(xiàn)過
                    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 開始搜索子串下一個(gè)出現(xiàn)的位置，如果找不到返回-1
                     * 嘗試在 string 的不同位置刪除同一子串，得到多種不同的結(jié)果，
                     * 加入隊(duì)列然后拋出，對(duì) dict 中子串(可以和上一次刪除的子串
                     * 相同)進(jìn)行下一次刪除
                     */
                    found = string.indexOf(sub, found + 1);
                }
            }
        }
        return min;
    }
}