可删除字母，需要多少次构造

14417335 发表于 2019/04/01 19:57:32
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=491464
是不是一样的？

版主帮我删了吧，我眼残了没翻到

kaipeng21 发表于 2019-4-1 21:08
版主帮我删了吧，我眼残了没翻到

合并就好。你提供的第二个例子不错。合并后会加米。

题目看了好久完全不懂怎么会提到binary search
感谢@yangyuzhiguang的代码一看就明白了

顺便贴个Python的两种版本

您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

写了一个贪心的解法，不确定有没有edge case没cover到。。

1. import collections
   
2. 
   
3. 
   
4. def min_str(src, target):
   
5.     dic = collections.defaultdict(list)
   
6.     for i, s in enumerate(src):
   
7.         dic[s].append(i)
   
8. 
   
9.     res = 0
   
10.     i = 0
    
11.     n = len(target)
    
12.     while i < n:
    
13.         j = i
    
14.         tmp_dic = collections.defaultdict(int)
    
15.         prev = None
    
16.         while j < n:
    
17.             a = target[j]
    
18.             if a not in dic:
    
19.                 return -1
    
20.             else:
    
21.                 tmp_dic[a] += 1
    
22.                 # case1: 若使用过的字符a数量 > dic里记录a的长度，则需要一个新的src, 对应Example 1
    
23.                 # case2: 若当前字符a在src的index小于其前一个字符的index, 则也需要一个新的src，对应Example 2
    
24.                 if tmp_dic[a] > len(dic[a]) or \
    
25.                         (prev is not None and dic[a][tmp_dic[a]-1] < prev):
    
26.                     break
    
27.                 prev = dic[a][tmp_dic[a] - 1]
    
28.             j += 1
    
29.         res += 1
    
30.         i = j
    
31.     return res
    
32. 
    
33. # Example 1
    
34. src = 'abcadb'
    
35. aim = 'aaaa'
    
36. print(min_str(src, aim))
    
37. 
    
38. # Example 2
    
39. src = 'abcdb'
    
40. aim = 'ba'
    
41. print(min_str(src, aim))
    
42. 
    
43. # Example 3
    
44. src = "aabaaaaabaaabbbbaaaa"
    
45. aim = "bbaabbbb"
    
46. print(min_str(src, aim))
    

复制代码

补充内容 (2019-4-6 05:33):
复杂度O(m+n)?

补充内容 (2019-4-6 05:34):
搞错了，复杂度是O(max(m, n))?

dlwlrma 发表于 2019-4-6 05:25
写了一个贪心的解法，不确定有没有edge case没cover到。。
[mw_shl_code=python,true]import collections
...

source = "bcaecbcd"
target = "dcbceacb"

测了一下我写的 unittest，这个没过

补充内容 (2019-4-11 06:04):
d  cbc  e  acb
只要四个但码return 了6个

kaipeng21 发表于 2019-4-11 06:02
source = "bcaecbcd"
target = "dcbceacb"

嗯嗯，之前思路不对，改了下:

1. import collections
   
2. 
   
3. 
   
4. def min_str(src, target):
   
5.     dic = collections.defaultdict(list)
   
6.     for i, s in enumerate(src):
   
7.         dic[s].append(i)
   
8. 
   
9.     res = 0
   
10.     i = 0
    
11.     n = len(target)
    
12.     while i < n:
    
13.         j = i
    
14.         tmp_dic = collections.defaultdict(int)
    
15.         prev_idx = None
    
16.         while j < n:
    
17.             a = target[j]
    
18.             if a not in dic:
    
19.                 return -1
    
20.             else:
    
21.                 tmp_dic[a] += 1
    
22.                 if tmp_dic[a] > len(dic[a]):
    
23.                     break
    
24.                 else:
    
25.                     cur_idx = dic[a][tmp_dic[a]-1]
    
26.                     if prev_idx is None:
    
27.                         prev_idx = cur_idx
    
28.                     elif prev_idx > cur_idx:
    
29.                         while tmp_dic[a] <= len(dic[a]) and prev_idx > dic[a][tmp_dic[a]-1]:
    
30.                             tmp_dic[a] += 1
    
31.                         if tmp_dic[a] > len(dic[a]):
    
32.                             break
    
33.                         prev_idx = dic[a][tmp_dic[a]-1]
    
34.                         # Reach the end of src. Need a new src
    
35.                         if prev_idx == len(src)-1:
    
36.                             break
    
37.             j += 1
    
38.         res += 1
    
39.         i = j
    
40.     return res
    
41. 
    
42. src = "bcaecbcd"
    
43. aim = "dcbceacb"
    
44. print(min_str(src, aim))
    
45. 
    
46. src = 'abcdb'
    
47. aim = 'ba'
    
48. print(min_str(src, aim))
    
49. 
    
50. src = 'abcadb'
    
51. aim = 'aaaa'
    
52. print(min_str(src, aim))
    
53. 
    
54. src = "aabaaaaabaaabbbbaaaa"
    
55. aim = "bbaabbbb"
    
56. print(min_str(src, aim))
    
57. 
    
58. 
    

复制代码