请教一个面试中的算法题

草帽路飞UU

一年在面试里被问了一个算法，当时思路很乱，很快就被面试官打断了。
一直念念不忘，现在正好在整理知识框架，把这个写了下，跟大家讨论下，是否这个思路是合理的，是否有补充。
题目：

写一段程序，删除字符串a中包含的字符串b，举例 输入a = "asdw",b = "sd" 返回 字符串 “aw”，并且测试这个程序。

1. def delInnerString(string, targtString):
   
2.     '''
   
3.     去除String字符串中的targtString片段，返回去除后的字符串
   
4.     :param String: 原始字符串
   
5.     :param tagetString: 待删除片段
   
6.     :return: result
   
7.     '''
   
8.     if not isinstance(string,str):
   
9.         raise TypeError("string is not a str.")
   
10.     if not isinstance(targtString,str):
    
11.         raise TypeError("targtString is not a str.")
    
12.     if len(string) < len(targtString):
    
13.         raise Exception('targtString lenght must large to string lenght.')
    
14.     result = []
    
15.     flag = False # 标志是否匹配到targtString
    
16.     i = 0
    
17.     tag = -1 # 记录匹配到后，截取的位置
    
18.     while i < len(string):
    
19.         j = 0
    
20.         while j < len(targtString):
    
21.             if i+j < len(string) and string[i+j] == targtString[j]:
    
22.                 j += 1
    
23.             else:
    
24.                 j += 1
    
25.                 flag = False
    
26.                 break
    
27.             flag = True
    
28.         if flag:
    
29.             tag = i+len(targtString)
    
30.         if i >= tag:
    
31.             result.append(string[i])
    
32.         i += 1
    
33.     return "".join(result)

复制代码

如何测试这段代码，我画了个思维导图：

附用例代码段

1. #a匹配不到b
   
2. assert delInnerString('', '') == ''
   
3. assert delInnerString('a', '') == 'a'
   
4. assert delInnerString('ab', '') == 'ab'
   
5. 
   
6. #a匹配到b部分一次
   
7. assert delInnerString('ab', 'ac') == 'ab'
   
8. assert delInnerString('cab', 'ac') == 'cab'
   
9. assert delInnerString('ba', 'ac') == 'ba'
   
10. 
    
11. #a匹配到b部分一次后，成功匹配到b
    
12. 
    
13. assert delInnerString('acab', 'ab') == 'ac'
    
14. assert delInnerString('aab', 'ab') == 'a'
    
15. 
    
16. #a完整匹配到b一次
    
17. assert delInnerString('a', 'a') == ''
    
18. assert delInnerString('ab', 'ab') == ''
    
19. assert delInnerString('bab', 'ab') == 'b'
    
20. assert delInnerString('babc', 'ab') == 'bc'
    
21. 
    
22. #a匹配到b一次，第二次部分匹配到b
    
23. assert delInnerString('aba', 'ab') == 'a'
    
24. assert delInnerString('abca', 'ab') == 'ca'
    
25. assert delInnerString('caba', 'ab') == 'ca'
    
26. assert delInnerString('cabca', 'ab') == 'cca'
    
27. 
    
28. #a匹配到b多次
    
29. assert delInnerString('aaaaaaaa', 'a') == ''
    
30. assert delInnerString('abababababab', 'ab') == ''
    
31. assert delInnerString('aaaabaaaa', 'a') == 'b'
    
32. assert delInnerString('baaaaaaaa', 'a') == 'b'
    
33. assert delInnerString('aaaaaaaab', 'a') == 'b'
    
34. 
    
35. #随机测试
    
36. assert delInnerString('asdwwdaaa', 'wd') == 'asdwaaa'
    
37. assert delInnerString('123d2e231', '0') == '123d2e231'
    
38. assert delInnerString('测试000', '测试') == '000'
    
39. assert delInnerString('\n', '') == '\n'
    
40. # 有重叠
    
41. assert delInnerString('ababa', 'aba') == ''
    
42. assert delInnerString('ccababacc', 'aba') == 'cccc'
    
43. assert delInnerString('abcabca', 'abca') == ''
    
44. 
    
45. # 一次截取后仍然包含目标字段
    
46. assert delInnerString('aabb','ab') == ''

复制代码

乐哈哈yoyo

&#128514; 讲真这个题目如果真实要用，我就直接一句解决了

1. “”.join(string.split(targetString))
   

复制代码

但是，面试这样会不太讨巧了吧？

八戒你干嘛

感觉代码还不够优雅

小爸爸

前面异常判断是加分项，而后面的if else就太啰嗦了。可以用indexOf来获取其实位置，然后substring就完事了

悠悠小仙仙

如果是 ababa aba
这种特殊情况呢，还需要确认顺序匹配还是倒序匹配