【每日一题20220415】文字合成

[hogwarts (霍格沃兹测试学院官方)]

‍ 在面试的时候有一道算法题，要求编写一个函数，判断一个给定的字符串s，能否可以由另外两个子串part1和part2合成。 注意，part1和part2中的字母原有顺序必须和s中出现的顺序是一致的。

【示例】
输入：s='hogwarts', part1='hws', part2='ogart'
输出：True
解释：因为hws和ogart的出现顺序和hogwarts一致，合成后也是hogwarts，因此是True

题目难度：困难
题目来源：CodeWars-Merged String Checker

def solution(s: str, part1: str, part2: str)-> bool:
    # your code here

assert solution('hogwarts','hws','ogart') is True
assert solution('codewars', 'code', 'wars') is True
assert solution('codewars', 'cod', 'wars') is False

[949645067_3107]

def solution(s: str, part1: str, part2: str) -> bool:
   # if len(s) != len(part1) + len(part2):
    #    return False
    cursor1 = cursor2 = 0
    for word in s:
        if cursor1 < len(part1) and word == part1[cursor1]:
            cursor1 += 1
        elif cursor2 < len(part2) and word == part2[cursor2]:
            cursor2 += 1
        else:
            return False
    return True

[1073434718_2599]

def solution(s: str, part1: str, part2: str)-> bool:
    # your code here
    part1_list = list(part1)
    part2_list = list(part2)
    for i in range(len(s)):
        if len(part1_list) != 0 and s[i] == part1_list[0]:
            part1_list.pop(0)
        elif len(part2_list) != 0 and s[i] == part2_list[0]:
            part2_list.pop(0)
        else:
            return False
    if len(part1_list) == 0 and len(part2_list) == 0:
        return True
    else:
        return False


assert solution('hogwarts','hws','ogart') is True
assert solution('codewars', 'code', 'wars') is True
assert solution('codewars', 'cod', 'wars') is False
assert solution('hogwartsworld','hwsrd','ogartwol') is True
assert solution('hogwartsworld','hwswod','ogartrl') is True

[ambiguous_moonlight]

def solution(s: str, part1: str, part2: str)-> bool:
    if sorted(s) != sorted(part1+part2):
        return False
     res1,res2= '',''
    for letter in s:
        if part1 !='' and part1[0] == letter:
            res1 += letter
            part1 = part1[1:]
        if part2 !='' and part2[0] == letter:
            res2 += letter
            part2 = part2[1:]
    if sorted(res1+res2) == sorted(s):
        return True
    else:
        return False

[455018255_7468]

def solution(s: str, part1: str, part2: str)-> bool:
    # your code here
    if len(s) != len(part1) + len(part2):
        return False
    for i in s:
        if len(part1) > 0 and i == part1[0]:
            part1 = part1.replace(i, '', 1)
        elif len(part2) > 0 and i == part2[0]:
            part2 = part2.replace(i, '', 1)
        else:
            return False
    else:
        return True
        

assert solution('hogwarts','hws','ogart') is True
assert solution('codewars', 'code', 'wars') is True
assert solution('codewars', 'cod', 'wars') is False
assert solution('sssyyysss', 'ssyys', 'syss') is True

[1402775654_8805]

assert solution(‘hwhharts’, ‘hhs’, ‘hwart’) is True
你们的答案执行这个会报错

[1073434718_2599]

你这个拆分的不对吧，w要在第二个h的前面，可以分成下面这样的
assert solution(“hwhharts”, “hwhs”, “hart”) is True
assert solution(“hwhharts”, “hhs”, “whart”) is True

[1208634117_0015]

def solution(s: str, part1: str, part2: str)-> bool:
    # your code here
    list1 = []
    a = s
    if len(s) != len(part1) + len(part2):
        return False
    else:
        for i in range(len(part1)):
            list1.append(a.find(part1[i]))
            a = a.replace(part1[i],"",1)
        print(list1)
        for j in part1:
            s = s.replace(j,"",1)
        print(s)
        if sorted(list1) == list1 and s == part2:
            return True
        else:
            return False


assert solution('hogwarts','hws','ogart') is True
assert solution('codewars', 'code', 'wars') is True
assert solution('codewars', 'cod', 'wars') is False

[LuckyStar]

def solution(s: str, part1: str, part2: str)-> bool:
# your code here
if len(s) != len(part1 + part2):
    return False
for i in s:
    if len(part1) > 0 and part1[0] == i:
        part1 = part1.replace(part1[0], "")
    elif len(part2) > 0 and part2[0] == i:
        part2 = part2.replace(part2[0], "")
    else:
        return False
return True


assert solution('hogwarts', 'hws', 'ogart') is True
assert solution('codewars', 'code', 'wars') is True
assert solution('codewars', 'cod', 'wars') is False

[1065493099 (tkndsg)]

大佬们的用例很犀利

def solution(s: str, part1: str, part2: str) -> bool:
    def func(s: str, part1: str, part2: str):
        new_str = ""
        for char in s:
            if char == part1[0]:
                new_str += part1[0]
                if len(part1) > 1:
                    part1 = part1[1::]
            else:
                new_str += part2[0]
                if len(part2) > 1:
                    part2 = part2[1::]
        return new_str == s
    return func(s, part1, part2) or func(s, part2, part1)

assert solution('hogwarts', 'hws', 'ogart') is True
assert solution('codewars', 'code', 'wars') is True
assert solution('codewars', 'cod', 'wars') is False
assert solution('sssyyysss', 'ssyys', 'syss') is True
assert solution('hwhharts', 'hhs', 'hwart') is True
assert solution('hogwartsworld','hwsrd','ogartwol') is True
assert solution('hogwartsworld','hwswod','ogartrl') is True

[1402775654_8805]

你貌似解决了先part2再part1的情况，但是情况更为复杂就不行了，assert solution(‘ababab’, ‘bab’, ‘aba ’) is True

[1065493099 (tkndsg)]

大佬给的这个断言，我前面的代码是能跑通的~
不过我明白大佬的意思 例如，下面我的这组cases，在座各位无人通过 ：

assert solution('hogwarts','hws','ogart') is True
assert solution('abaaabaa', 'abaa', 'aaab') is True
assert solution('codewars', 'cod', 'wars') is False
assert solution('haah', 'ha', 'ha') is False

······
所以我又写了一个新方法，求更犀利的cases：

def solution(s: str, part1: str, part2: str) -> bool:
    if len(s) - len(part1) - len(part2) != 0:
        return False

    def func(s, part1, part2):
        if len(s) == len(part1) == len(part2) == 0:
            return True
        if len(part1) > 0 and s[0] == part1[0]:
            return func(s[1::], part1[1::], part2) or func(s[1::], part2, part1[1::])
        elif len(part2) > 0 and s[0] == part2[0]:
            return func(s[1::], part1, part2[1::]) or func(s[1::], part2[1::], part1)
        return False
    return func(s, part1, part2) or func(s, part2, part1)

[1727375395_3146]

    def solution(s: str, part1: str, part2: str) -> bool:
        if len(part1)+len(part2) != len(s):return False
        s1,s2 = '',''
        for i in s:
            if i in part1:s1 += i
            if i in part2:s2 += i
        for i in part1:
            if i not in s1:return False
        for i in part2:
            if i not in s2:return False
        return True

[1727375395_3146]

因为 ‘haah’ 只有一个子串 ‘ha’
所以 那条断言不符合题意

[1065493099 (tkndsg)]

子串随便加啊，我是把出问题的点专门精简出来了，下面的字符串符合题意了吗？

assert solution('haahheihei', 'haheihei', 'ha') is False

[1304543605_9753]

如果s为codewarts,part1为code，part2为wartss，执行结果就会不对；
另外s有重复字符，比如hologwarts part1为howts,part2为olgar,执行结果也不对

[949645067_3107]

第一个一个错误取消前两行的注释,第二个是本来你输入的就不符合

[zhengang12_0513]

x, y = 0, 0
    for i in range(len(s)):
        if x < len(part1) and s[i] == part1[x]:
            x = x + 1
            continue
        elif y < len(part2) and s[i] == part2[y]:
            y = y + 1
            continue
        else:
            return False
    if len(s) == x + y and x + y == len(part2) + len(part1):
        return True
    else:
        return False

[1065493099 (tkndsg)]

assert solution('haah', 'ha', 'ha') is False

这条用例到底怎么不符合题意了？题目中哪里提到？烦请赐教 @1727375395_3146

另外你说的：

‘haah’ 只有一个子串 ‘ha’

是认真的吗？ 'haah’的子串有：‘h’, ‘a’, ‘ha’, ‘aa’, ‘ah’, ‘haa’, ‘aah’, ‘haah’, ‘’ 呢

[joyoko (徐子宇)]

最开始用遍历后pop的方法，发现有许多情况没考虑到，最后借鉴大佬们的思路一起套娃。

def solution(s: str, part1: str, part2: str)-> bool:
    if len(s) <= 1:
        return s == part1 + part2
    elif len(part1) > 0 and len(part2) > 0 and s[0] == part1[0] and s[0] == part2[0]:
        return solution(s[1:], part1[1:], part2) or solution(s[1:], part1, part2[1:])
    elif len(part1) > 0 and s[0] == part1[0]:
        return solution(s[1:], part1[1:], part2)
    elif len(part2) > 0 and s[0] == part2[0]:
        return solution(s[1:], part1, part2[1:])
    return False