草帽路飞UU 发表于 2017-6-28 11:50:01

请教一个面试中的算法题

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

写一段程序，删除字符串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 == targtString:
                j += 1
            else:
                j += 1
                flag = False
                break
            flag = True
      if flag:
            tag = i+len(targtString)
      if i >= tag:
            result.append(string)
      i += 1
    return "".join(result)
如何测试这段代码，我画了个思维导图：
https://testerhome.com/uploads/photo/2017/da45cf20b571b68ddc139b680db64f16.gif!large
附用例代码段#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') == ''




乐哈哈yoyo 发表于 2017-6-28 15:49:22

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

“”.join(string.split(targetString))
但是，面试这样会不太讨巧了吧？

八戒你干嘛 发表于 2017-6-28 15:49:52

感觉代码还不够优雅

小爸爸 发表于 2017-6-28 15:50:55

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

悠悠小仙仙 发表于 2017-6-28 15:51:29

如果是 ababa aba
这种特殊情况呢，还需要确认顺序匹配还是倒序匹配
页: [1]
查看完整版本: 请教一个面试中的算法题