Remove Substrings

Difficulty : Medium

Given a string s and a set of n substrings. You are supposed to remove every instance of those n substrings from s so that s is of the minimum length and output this minimum length.

Have you met this question in a real interview? Yes
Example
Given s = ccdaabcdbb, substrs = ["ab", "cd"]
Return 2

Explanation:
ccdaabcdbb -> ccdacdbb -> cabb -> cb (length = 2)

注意一下String.indexOf()的用法

indexOf(int ch)
Returns the index within this string of the first occurrence of 
the specified character.

indexOf(int ch, int fromIndex)
Returns the index within this string of the first occurrence of 
the specified character, starting the search at the specified index.

indexOf(String s)
Returns the index within this string of the first occurrence of 
the specified substring.

indexOf(String] str, int fromIndex)
Returns the index within this string of the first occurrence of 
the specified substring, starting at the specified index.

这道题一开始没看出来是用BFS来做，看了答案才发现。用一个Queue来装s每一次去掉一个substr所剩下的newString, 同时用一个HashSet来记录访问过哪些newString. 宽度优先体现在每一次都是对poll()出来的s去掉一个长度的sub, 而不是一次连续去掉很多个。这样每一层次存下来minLength, 等最短的被poll()出来，还剩下的newString的长度就是我们要求的。

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) {
        // Write your code here
        int minLength = s.length();
        if (s == null || s.length() == 0){
            return 0;
        } 
        if (dict == null || dict.size() == 0){
            return minLength;
        }
        Queue<String> queue = new LinkedList<>();
        Set<String> hash = new HashSet<>();
        queue.offer(s);
        hash.add(s);
        
        while (!queue.isEmpty()){
            String curt = queue.poll();
            for (String sub : dict){
                int found = curt.indexOf(sub);
                while (found != -1){
                    String newString = curt.substring(0, found) + curt.substring(found + sub.length(), curt.length());
                    if (newString.length() < minLength){
                        minLength = newString.length();
                    }
                    if (!hash.contains(newString)){
                        queue.offer(newString);
                        hash.add(newString);
                    }
                    found = curt.indexOf(sub, found + 1);
                }
            }
        }
        return minLength;
    }
}