新手区 请教一个面试中的算法题

剪烛 · 2017年03月28日 · 最后由 剪烛 回复于 2020年03月11日 · 150 次阅读

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

题目:

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

代码:(更新在#9 楼

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
    i = 0
    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:
            i += len(targtString)
        else:
            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') == ''

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
共收到 38 条回复 时间 点赞

😂好厉害

感觉代码还不够优雅

恒温 回复

😂 讲真这个题目如果真实要用,我就直接一句解决了

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

但是,面试这样会不太讨巧了吧?

😂 这已经是我的最高水准了

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

易寒 回复

人家是要求不能用这些内置函数

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

Michael_Wang 回复


确实没有考虑到重叠的问题,容我想一想

Michael_Wang 回复

我改了下,以支持这种匹配时,可能出现重叠而导致只匹配第一个的情况

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)

相应的,路径覆盖还增加:

# 有重叠
assert delInnerString('ababa', 'aba') == ''
assert delInnerString('ccababacc', 'aba') == 'cccc'
assert delInnerString('abcabca', 'abca') == ''
剪烛 回复

你这精神,直接给你 p6 了。

剪烛 #11 · 2017年03月29日 Author
恒温 回复

😆 😆 😆 😆
是因为我要准备面试

我觉得重叠问题有点过度设计了。while 看的头晕,你不如直接用伪语言说说思路就可以了。

剪烛 #13 · 2017年03月30日 Author

我也觉得是,伪代码简明,但是用 python 实现,总束手束脚的

string #字符串
targetString # 匹配字符串
result #输出结果
tag = -1 #截取的游标
for i=0,i<len(string)-len(targetString),i++:#循环遍历一次string
  if string[i:i+j] ==  tartgetString#如果匹配成功,则把游标放在匹配片段的最后一个位置
     tag = i+j
  else:
    if i <= tag: #当前位置i到tag游标的位置不予截取,否则添加进result
        result += string[i] #当前位置的字符添加进result
return result

简单用 java 实现了,如果要求永不包含 b,则再加个递归就好了

public String test(String str, String targetStr) {
        StringBuffer sb = new StringBuffer();
        if(str==null||targetStr==null)
            return sb.toString();
        if (str.length() > =targetStr.length()) {
            for (int i = 0; i < str.length(); i++) {
                if ((i + targetStr.length()) > str.length()) {
                    sb.append(str.substring(i, str.length()));
                    break;
                }
                if (!str.substring(i, (i + targetStr.length())).equals(targetStr)) {
                    sb.append(str.substring(i, i + 1));
                } else {
                    i = i + targetStr.length() - 1;
                }
            }
        } else
            sb.append(str);
        return sb.toString();
    }
剪烛 #15 · 2017年03月31日 Author
xwgoss 回复

请教一下,什么叫永不包含 b 呢?

剪烛 回复

str="aadd"
targetStr="ad"
这样删除一次后,自然还会有 “ad”。若要永不包含,则递归删除即可。不过慎用递归,上次面试因为递归没考虑仔细写了个死循环,导致 game over😂

一年前还记得,老厉害了

—— 来自 TesterHome 官方 安卓客户端

剪烛 #18 · 2017年03月31日 Author
xwgoss 回复

😂 妈呀,又是一种情况没有考虑到

xwgoss 回复

这个赞

#-- coding: utf-8 --

#!/usr/bin/python
import unittest
'''
写一段程序,删除字符串 a 中包含的字符串 b,举例 输入 a = "asdqwe",b = "sd" 返回 字符串 “aw”,并且测试这个程序。
'''

def delInnerString(a,b):
    if not isinstance(a,str):
        raise TypeError('a is not a str.')
    if not isinstance(b,str):
        raise TypeError('b is not a str.')
    result=a[:];
    i=0;
    j=0;
    la=len(a);
    lb=len(b);
    tag=False;
    while i<(la-lb+1):
        #print 'i='+str(i);
        #print a[i:i+len(b)]
        if a[i:i+lb]==b:
            tag=True;
            result=a[:i]+a[i+lb:];
            break;
        else:
            i+=1;
    #print result;
    return result;

class TestdelInnerStringFunctions(unittest.TestCase):
    def setUp(self):
        pass
    def tearDown(self):
        pass
    def test_nomorl1(self):
        self.assertEqual(delInnerString('asdqwe','we'),'asdq','test pass');
    def test_nomorl2(self):
        self.assertEqual(delInnerString('asdqwe','0'),'asdqwe','test pass');
    def test_nomorl3(self):
        self.assertEqual(delInnerString('测试asdqwe','we'),'测试asdq','test pass');
    def test_nomorl4(self):
        self.assertEqual(delInnerString('测试asdqwe','测试'),'asdqwe','test pass');
    def test_nomorl5(self):
        self.assertEqual(delInnerString('asdqwe',''),'asdqwe','test pass');
    def test_nomorl6(self):
        self.assertEqual(delInnerString('',0),'','test fail');
    def test_nomorl7(self):
        self.assertEqual(delInnerString(0,'as'),'','test fail');
    def test_nomorl8(self):
        self.assertEqual(delInnerString(True),'','test fail');
    def test_nomorl9(self):
        self.assertEqual(delInnerString(),'','test fail');

if __name__ =='__main__':
    unittest.main()

----看到版主的思维导图,厉害,
第一次发布不会排版,求指教

@shixue33 楼主看看这个行不?话说楼主的 case 真全,我忘了考虑 b 为空,一直死循环。


def split_loop(a, b):
    if not isinstance(a, str) or not isinstance(b, str) :
        raise TypeError("one of them not string.")
    while b in a:
        if a == '' or b =='':
            return a                    
        for i in range(len(a)-len(b)+1):
            if a[i:i+len(b)] == b:
                if i == 0:
                    a = a[len(b):]
                elif i == (len(b) - len(b) -1):
                    a = a[:i]
                else:
                    a =  a[:i] + a[i+len(b):]
    return a

剪烛 #22 · 2017年04月04日 Author
alam.zheng 回复

😂 markdown 有语法可以显示代码块,三个`

剪烛 #23 · 2017年04月04日 Author
mrleopard 回复

😂 你都用 a in b 了,为啥还辛辛苦苦循环,不直接 find 就好了呢

剪烛 回复

可以了,谢谢

剪烛 回复

见笑了,我的理解不用 string 的内置函数,in 好像不是,find 就不同了。

剪烛 回复

assert (delInnerString("111","11") =="1")
111 里面删掉 11 之后不再包含 11 了,中间这个 1 你能删两次?

没有考虑用正则么

考算法就不能不考虑两个问题,空间复杂度和时间复杂度。这个题目主要考虑下时间复杂度,你当前的算法的时间复杂度,最悲观是应该是 O(i*j),两个字符串的长度越长,你这个算法耗时成指数增长,假设每次第 i 个字符开始匹配,匹配到第 j-1 个字符就失败,这个时间绝对让你崩溃。

换个思路:把源字符串 source 按目标字符串 target 的长度来切割,然后匹配切割出来的字符串是否和 target 相等,那么时间复杂度就是 O(i-j) 就是线性的

java 代码:

  for(int i = 0 ; i < source.length-target.length; i ++){
    if(source.substring(i,i+target.length)!=target){
      result+=source.chartAt(i);
      i++;
    }else{
      i+=target.length;
    }
}
chenDoInG 回复

这个思路赞,简洁

嵌套循坏的时间复杂度太高,面试官肯定不满意。
考虑把 string 逐个字符压栈,栈顶包含 targetstring 的部分出栈,最后栈里剩下的就是想要的结果了,复杂度 O(n)

如果要求的匹配的字符串,比被匹配的字符串还要长呢?

34楼 已删除

感觉写的好麻烦啊。写个简单的版本。

def f(str1, str2):
    list1 = list(str1)
    list2 = list(str2)
    new_list = []
    for i in list1:
        if not list2.__contains__(i):
            new_list.append(i)
    new_str = "".join(new_list)
    return new_str
36楼 已删除

a="asdw"
b="sd"
c = a
def delStr(a,b,c):
for i in a:
for j in b:
if i==j:
c = c.replace(i,"")
return c

print(delStr(a,b,c))

想太少😂

这样的,上面格式没调好

剪烛 #40 · 2020年03月11日 Author
刘粒粒 回复

😂 感觉这种写法有点奇怪。要莫名其妙多好多无用的 replace。要能这样写,为啥不直接 a.replace(b,"") 呢?

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册