Google

Google 暑期实习电话面算法题。

Phone Interview

Compare keyboard events sequences

# abc123\b123\b  -> abc1212
# abc1212        -> abc1212

Time O(n), Space O(n)

def convert(s):
    res = []
    index = 0
    for i in range(len(s)):
        # abc12123
        if s[i] != '\b':
            if len(res) == index:
                res.append(s[i])
            else:
                res[index] = s[i]
            index += 1
        else:
            if index == 0:
                continue
            else:
                index -= 1
        return ''.join(res[:index])

def compare(s1, s2):
    return convert(s1) == convert(s2)

Time O(n), Space O(1)

def get_char(s, p):
    cnt = 0
    while p >= 0 and (cnt > 0 or s[p] == '\b'):
        if s[p] == '\b':
            cnt += 1
        else:
            cnt -= 1
        p -= 1
    return p

def compare_(s1, s2):
        p1 = len(s1) - 1
        p2 = len(s2) - 1

        while p1 >= 0 and p2 >= 0:
            p1 = get_char(s1, p1)
            p2 = get_char(s2, p2)

            if p1 >= 0 and p2 >= 0:
                if s1[p1] != s2[p2]:
                    return False
                else:
                    p1 -= 1
                    p2 -= 1

        p1 = get_char(s1, p1)
        p2 = get_char(s2, p2)
        return p1 < 0 and p2 < 0

• 能抽象就抽象。多写几个函数。

Test Case

assert(compare_('', '2\b') == True)
assert(compare_('', '12\b') == False)
assert(compare_('1', '12\b') == True)
assert(compare_('', '\b2\b') == True)
assert(compare_('', '12\b2\b') == False)
assert(compare_('1', '123\b2\b\b') == True)