如何更正比较包含按键的两个字符串的算法？

Question

如果两个字符串相等，这就是返回true的算法。字符串可能包含类似backspace的按键。代码使用光标和指针遍历字符串中的每个字母，如果找到按键，则跳过2个位置（即.\b）

#!/usr/bin/env python
import argparse
import __builtin__

# Given two different strings, one with backspaces (keypresses), find if they are equivalent or not

def main():
    parser = argparse.ArgumentParser(description="Enter two strings without or without backspaces")
    parser.add_argument("s1", type=str, help="The first string.")
    parser.add_argument("s2", type=str, help="The second string.")
    args = parser.parse_args()
    print(compare(args.s1, args.s2))

def compare(s1, s2):
    BACKSPACE = '\b'
    cursor = 0;
    pointer1 = 0; pointer2 = 0; # current position in backspaced string. 

    canon_len1 = len(s1); canon_len2 = len(s2); # length of the canonical string

    num_diff = 0
    while True:
        if s1[pointer1] == BACKSPACE or s2[pointer2] == BACKSPACE:
            # decrement the cursor and undo the previous compare
            cursor -= 1; 
            if s1[cursor] != s2[cursor]:
                num_diff -= 1
            # decrement the canonical lengths appropriately
            canon_len1 -= 2 if s1[pointer1] == BACKSPACE else 0
            canon_len2 -= 2 if s2[pointer2] == BACKSPACE else 0
        else:

            if s1[pointer1] != s2[pointer2]:
                num_diff += 1
            cursor += 1

        # increment the pointers, making sure we don't run off then end 
        pointer1 += 1; pointer2 += 1;
        if pointer1 == len(s1) and pointer2 == len(s2):
            break
        if pointer1 == len(s1): pointer1 -= 1
        if pointer2 == len(s2): pointer2 -= 1

    return num_diff == 0 and canon_len1 == canon_len2

if __name__ == "__main__":
    main()

#!/usr/bin/env python

import compare_strings
import unittest

class compare_strings_test(unittest.TestCase):

    def test_01(self):
        raised = False
        try:
            compare_strings.compare('Toronto', 'Cleveland')
        except:
            raised = True
        self.assertFalse(raised, 'Exception raised')

    def test_02(self):
        equivalent = compare_strings.compare('Toronto', 'Cleveland')
        self.assertEquals(equivalent, False)

    def test_03(self):
        equivalent = compare_strings.compare('Toronto', 'Toroo\b\bnto')
        self.assertEquals(equivalent, False)

    def test_04(self):
        equivalent = compare_strings.compare('Toronto', 'Torooo\b\bntt\bo')
        self.assertEquals(equivalent, True)

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

...F
======================================================================
FAIL: test_04 (__main__.compare_strings_test)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "compare_strings_test.py", line 26, in test_04
    self.assertEquals(equivalent, True)
AssertionError: False != True

----------------------------------------------------------------------
Ran 4 tests in 0.001s

测试4失败，但是“Toronto”和“Torooo\b\bntt\bo”应该是相等的减去backspaces

Answer 1

我相信您当前代码中的问题源于这样一个事实：您可以在一行中有多个backspace，但是您只查看“一”个字符。（这一点我可能错了，我没有用pdb检查代码。）

正如评论中所建议的，解决这个问题的一个好方法是将其分为以下两部分。你知道吗

1. 规范化/规范化两个输入字符串。这意味着一次处理一个字符，从每个字符串中去掉backspace和前面的相关字符。你知道吗
2. 比较两个规范化的字符串。你知道吗

步骤2很简单，只需使用python中内置的stringcompare方法（==）。你知道吗

步骤1有点困难，因为在输入字符串的一行中可能有多个backspace。处理这个问题的一种方法是建立一个新的字符串，一次一个字符，然后在每个空格上删除最后添加的字符。下面是一些示例代码。你知道吗

def canonicalize(s):
    normalized_s = ""
    for i, c in enumerate(s):
        # Check for a backspace, taking care not to run off the end of the string.
        if c == BACKSPACE:
            normalized_s = normalized_s[:-1]
        else:
            normalized_s += c

    return normalized_s

这种方法的一个很好的副作用是，前导的backspace不会导致任何错误，它们被忽略了。稍后我将尝试在其他实现中保留此属性。在c++这样的语言中，可以修改字符串，这样的代码可以变得非常有效，因为这类似于将指针和条目更改为char数组。你知道吗

在python中，每次编辑都会创建一个新字符串（或者至少不能保证它不会分配一个新字符串）。我认为关注自己的堆栈（也就是一个由字符组成的数组，指针指向末尾）可以产生更好的代码。在python中有几种管理堆栈的方法，最常见的是列表，另一个好的选择是收藏.deque. 除非分析人员另有说明，否则我会选择更熟悉的列表。你知道吗

def canonicalize(s):
    normalized_s = list()
    for c in s:
        # Check for a backspace, taking care not to run off the end of the string.
        if c == BACKSPACE:
            if normalized_s:
                normalized_s.pop()
        else:
            normalized_s.append(c)

    return "".join(normalized_s)

最后的比较方法可能看起来像

def compare(s1, s2):
    return canonicalize(s1) == canonlicalize(s2)

---

上面的代码有两个问题。首先，它几乎可以保证创建两个新字符串。第二个是它需要对字符串进行四次总的传递，每个输入字符串一次，每个清理过的字符串一次。你知道吗

这可以通过向后而不是向前改进。通过向后迭代，可以看到backspaces，并提前知道哪些字符将被删除（read-ignored或skipped）。我们一直这样做，直到出现不匹配，或者至少有一个字符串的字符用完为止。这种方法需要更多的簿记，但不需要额外的空间。它只使用两个指针跟踪每个字符串的当前进度，并使用一个计数器跟踪要忽略的字符数。下面给出的代码不是特别python的，它可以做得更好。如果你要用两台发电机和一台izipèu，你可以把所有的样板都去掉。你知道吗

def compare(s1, s2):
    i, j = len(s1) - 1, len(s2) - 1

    while i >= 0 or j >= 0:
        ignore = 0
        while i >= 0:
            if s1[i] == BACKSPACE:
                ignore += 1
            elif ignore > 0:
                ignore -= 1
            else:
                break
            i -= 1

        ignore = 0
        while j >= 0:
            if s2[j] == BACKSPACE:
                ignore += 1
            elif ignore > 0:
                ignore -= 1
            else:
                break
            j -= 1

        if i < 0 and j < 0:
            # No more characters to try and match
            return True

        if (i < 0 and j >= 0) or (i >= 0 and j < 0):
            # One string exhausted before the other
            return False

        if s1[i] != s2[j]:
            return False

        i -= 1
        j -= 1

    return True

---

编辑

下面是我为compare的上一个实现尝试的一些测试用例。你知道吗

true_testcases = (
    ("abc", "abc"),
    ("abc", "abcde\b\b"),
    ("abcdef", "\b\babcdef\bf"),
    ("", "\b\b\b"),
    ("Toronto", "Torooo\b\bntt\bo"))

false_testcases = (
    ("a", "a\b"),
    ("a", "a\b\b"),
    ("abc", "abc\bd\be"),
)

print([eq(s1, s2) for s1, s2 in true_testcases])
print([eq(s1, s2) for s1, s2 in false_testcases])