Bloomberg 面筋题 candy crush follow up 如何解决

https://leetcode.com/discuss/int ... n-or-Candy-Crush-1D

如题 大家帮忙看下 这个 题目

我觉得这个 follow up 有点难 要怎么解决 remove 后的子串呢

用backtrack可以吗？每次碰到k >= 3的consecutive，先remove掉（可以用s.substring）然后进行下一个recursion，同时维护一个global的res来记录最短的字符串长度；如果remove后能够得到比当前res更小的，就继续那个branch，否则把remove掉的还回来，继续下一轮check。不知道说的对不对哈哈

lz能讲一下这个follow-up和原题的区别在哪么。。。没看懂。非常感谢

这道题印象太深刻了，在leetcode上也算很难的题了: https://leetcode.com/problems/remove-boxes/

1. def candy2(s):
   
2. 
   
3.     res = dfs(s)
   
4.     return res
   
5. 
   
6. @lru_cache
   
7. def dfs(s):
   
8.     if not s:
   
9.         return ""
   
10.    
    
11.     j = 0
    
12.     i = 1
    
13.     count = 1
    
14.     res = s
    
15.     while i < len(s):
    
16.         if s[i] == s[i - 1]:
    
17.             count += 1
    
18.             i += 1
    
19.         elif s[i] != s[i - 1]:
    
20.             if count >= 3:
    
21.                 new_s = s[0:j] + s[i:]
    
22.                 ans = dfs(new_s)
    
23.                 if len(ans) < len(res):
    
24.                     res = ans
    
25.             count = 1
    
26.             j = i
    
27.             i += 1
    
28.         
    
29.     return res

复制代码