51Testing软件测试论坛

标题: 请教一个面试中的算法题 [打印本页]
作者: 草帽路飞UU    时间: 2017-6-28 11:50
标题: 请教一个面试中的算法题
一年在面试里被问了一个算法，当时思路很乱，很快就被面试官打断了。
一直念念不忘，现在正好在整理知识框架，把这个写了下，跟大家讨论下，是否这个思路是合理的，是否有补充。
题目：

写一段程序，删除字符串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'

  6. #a匹配到b部分一次
  7. assert delInnerString('ab', 'ac') == 'ab'
  8. assert delInnerString('cab', 'ac') == 'cab'
  9. assert delInnerString('ba', 'ac') == 'ba'

  11. #a匹配到b部分一次后，成功匹配到b

  13. assert delInnerString('acab', 'ab') == 'ac'
  14. assert delInnerString('aab', 'ab') == 'a'

  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'

  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'

  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'

  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') == ''

  45. # 一次截取后仍然包含目标字段
  46. assert delInnerString('aabb','ab') == ''
复制代码





作者: 乐哈哈yoyo    时间: 2017-6-28 15:49
&#128514; 讲真这个题目如果真实要用，我就直接一句解决了

  1. “”.join(string.split(targetString))
复制代码
但是，面试这样会不太讨巧了吧？
作者: 八戒你干嘛    时间: 2017-6-28 15:49
感觉代码还不够优雅
作者: 小爸爸    时间: 2017-6-28 15:50
前面异常判断是加分项，而后面的if else就太啰嗦了。可以用indexOf来获取其实位置，然后substring就完事了
作者: 悠悠小仙仙    时间: 2017-6-28 15:51
如果是 ababa aba
这种特殊情况呢，还需要确认顺序匹配还是倒序匹配



欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/) Powered by Discuz! X3.2