|
一年在面试里被问了一个算法,当时思路很乱,很快就被面试官打断了。
一直念念不忘,现在正好在整理知识框架,把这个写了下,跟大家讨论下,是否这个思路是合理的,是否有补充。
题目:
写一段程序,删除字符串a中包含的字符串b,举例 输入a = "asdw",b = "sd" 返回 字符串 “aw”,并且测试这个程序。
- def delInnerString(string, targtString):
- '''
- 去除String字符串中的targtString片段,返回去除后的字符串
- :param String: 原始字符串
- :param tagetString: 待删除片段
- :return: result
- '''
- if not isinstance(string,str):
- raise TypeError("string is not a str.")
- if not isinstance(targtString,str):
- raise TypeError("targtString is not a str.")
- if len(string) < len(targtString):
- raise Exception('targtString lenght must large to string lenght.')
- result = []
- flag = False # 标志是否匹配到targtString
- i = 0
- tag = -1 # 记录匹配到后,截取的位置
- while i < len(string):
- j = 0
- while j < len(targtString):
- if i+j < len(string) and string[i+j] == targtString[j]:
- j += 1
- else:
- j += 1
- flag = False
- break
- flag = True
- if flag:
- tag = i+len(targtString)
- if i >= tag:
- result.append(string[i])
- i += 1
- return "".join(result)
复制代码
如何测试这段代码,我画了个思维导图:
附用例代码段- #a匹配不到b
- assert delInnerString('', '') == ''
- assert delInnerString('a', '') == 'a'
- assert delInnerString('ab', '') == 'ab'
- #a匹配到b部分一次
- assert delInnerString('ab', 'ac') == 'ab'
- assert delInnerString('cab', 'ac') == 'cab'
- assert delInnerString('ba', 'ac') == 'ba'
- #a匹配到b部分一次后,成功匹配到b
- assert delInnerString('acab', 'ab') == 'ac'
- assert delInnerString('aab', 'ab') == 'a'
- #a完整匹配到b一次
- assert delInnerString('a', 'a') == ''
- assert delInnerString('ab', 'ab') == ''
- assert delInnerString('bab', 'ab') == 'b'
- assert delInnerString('babc', 'ab') == 'bc'
- #a匹配到b一次,第二次部分匹配到b
- assert delInnerString('aba', 'ab') == 'a'
- assert delInnerString('abca', 'ab') == 'ca'
- assert delInnerString('caba', 'ab') == 'ca'
- assert delInnerString('cabca', 'ab') == 'cca'
- #a匹配到b多次
- assert delInnerString('aaaaaaaa', 'a') == ''
- assert delInnerString('abababababab', 'ab') == ''
- assert delInnerString('aaaabaaaa', 'a') == 'b'
- assert delInnerString('baaaaaaaa', 'a') == 'b'
- assert delInnerString('aaaaaaaab', 'a') == 'b'
- #随机测试
- assert delInnerString('asdwwdaaa', 'wd') == 'asdwaaa'
- assert delInnerString('123d2e231', '0') == '123d2e231'
- assert delInnerString('测试000', '测试') == '000'
- assert delInnerString('\n', '') == '\n'
- # 有重叠
- assert delInnerString('ababa', 'aba') == ''
- assert delInnerString('ccababacc', 'aba') == 'cccc'
- assert delInnerString('abcabca', 'abca') == ''
- # 一次截取后仍然包含目标字段
- assert delInnerString('aabb','ab') == ''
复制代码
|
|