Remove substrings from a string to get the minimum length

原贴：http://www.1point3acres.com/bbs/ ... 6orderby%3Ddateline
题目是这样的:
You are 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. Eg:
S- ccdaabcdbb . 1point 3acres 璁哄潧
n=2 - substrings-- (ab, cd). 涓

不知道为什么，问题里没有完全显示我问的内容。
我想说的是，我看了原帖主的解答，但是完全没看懂……能请哪位指教一下思路吗？

public int minLength(String s, Set<String> dict) {
        if(s.length() == 0){
            return 0;
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer(s);
        Set<String> set = new HashSet<>();
        int result = Integer.MAX_VALUE;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i ++){
                String head = queue.poll();
                for(String word : dict){
                    int index = head.indexOf(word);
                    while(index != -1){
                         String newStr = head.substring(0, index) +
                               head.substring(index + word.length(), head.length());
                    if(!set.contains(newStr)){
                        set.add(newStr);
                        queue.offer(newStr);
                        result = Math.min(result, newStr.length());
                    }
                    index = head.indexOf(word, index + 1);
                    }
                }
            }
        }
        return result;
    }

直接dfs + memo。。暴力总能出来的

1. 
   
2. 
   
3. from sets import Set
   
4. 
   
5. def removeSubstringsFromDictDriver(s, dic):
   
6.     if not s or not dic: return 0
   
7.     m = Set()
   
8.     l = [2**32-1]
   
9. 
   
10.     def removeSubstringsFromDict(s, dic, memo):
    
11.         if not s:
    
12.             l[0] = 0
    
13.             return
    
14.         if s in memo: return
    
15.         memo.add(s)
    
16.         if all([s.find(w) == -1 for w in dic]):
    
17.             l[0] = min(l[0], len(s))
    
18. 
    
19.         candidates = [s.replace(w, "", 1) for w in dic]
    
20.         for c in candidates:
    
21.             removeSubstringsFromDict(c, dic, memo)
    
22.         return
    
23. 
    
24.     removeSubstringsFromDict(s, dic, m)
    
25. 
    
26.     return l[0]
    
27. 
    
28. def main():
    
29.     s = 'ccdaabcdbb'
    
30.     d = Set(['ab', 'cd'])
    
31. 
    
32.     n = removeSubstringsFromDictDriver(s, d)
    
33. 
    
34.     print n
    
35. 
    
36. if __name__ == "__main__":
    
37.     main()
    

复制代码

看原来发的帖也不是dp，至少要利用前面的结果来计算下一个。和我的一样本质上是dfs + memo。‘
这个问题和8皇后是一样的。

saklyn 发表于 2017-7-25 10:12
看原来发的帖也不是dp，至少要利用前面的结果来计算下一个。和我的一样本质上是dfs + memo。‘
这个问题和 ...

请问设置这个 l = [2**32-1] 的目的是什么  不能直接以一个变量记录当前的最小值吗？

2011051305 发表于 2017-7-28 13:42
请问设置这个 l = [2**32-1] 的目的是什么  不能直接以一个变量记录当前的最小值吗？

应该是 l = [2**31-1]。这个是python的特点。如果c++/java应该是 l = INT_MAX 这样。

lintcode 624  Remove Substrings  应该是这个吧

时间复杂度上比较好的解法是这样的(写起来会很长）
先用KMP找到所有的匹配 (其实应该用AC自动机)

然后在每一个可能的匹配点上dp

总的来说dp部分和memo是一样的，但是AC自动机比暴力匹配算法还是要快不少。。