Lintcode 624. Remove Substrings

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.

Example

Example 1:

Input:
"ccdaabcdbb"
["ab","cd"]
Output:
2
Explanation: 
ccdaabcdbb -> ccdacdbb -> cabb -> cb (length = 2)

Example 2:

Input:
"abcabd"
["ab","abcd"]
Output:
0
Explanation: 
abcabd -> abcd -> "" (length = 0)

Solution: 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) {
        // write your code here
        if (s == null || s.length() == 0) {
            return 0;
        }

        if (dict == null || dict.size() == 0) {
            return s.length();
        }

        // BFS
        //
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(s);
        visited.add(s);

        int ans = s.length();

        while (!queue.isEmpty()) {
            String curStr = queue.poll();
            for (String dictWord : dict) {
                for (int i = 0; i < curStr.length(); i++) {
                    int startIdx = curStr.indexOf(dictWord, i);
                    if (startIdx != -1) {
                        String newStr = curStr.substring(0, startIdx) + curStr.substring(startIdx + dictWord.length());
                        
                        if (newStr.length() < ans) {
                            ans = newStr.length();
                        }

                        if (!visited.contains(newStr)) {
                            queue.offer(newStr);
                            visited.add(newStr);
                        }
                    }
                }
            }
        }

        return ans;
    }
}