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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

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;     } }