如果两个字符串相等,这就是返回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
最好事先使用如下函数从字符串中删除退格:
然后比较。你知道吗
我相信您当前代码中的问题源于这样一个事实:您可以在一行中有多个backspace,但是您只查看“一”个字符。(这一点我可能错了,我没有用pdb检查代码。)
正如评论中所建议的,解决这个问题的一个好方法是将其分为以下两部分。你知道吗
步骤2很简单,只需使用python中内置的stringcompare方法(==)。你知道吗
步骤1有点困难,因为在输入字符串的一行中可能有多个backspace。处理这个问题的一种方法是建立一个新的字符串,一次一个字符,然后在每个空格上删除最后添加的字符。下面是一些示例代码。你知道吗
这种方法的一个很好的副作用是,前导的backspace不会导致任何错误,它们被忽略了。稍后我将尝试在其他实现中保留此属性。在c++这样的语言中,可以修改字符串,这样的代码可以变得非常有效,因为这类似于将指针和条目更改为char数组。你知道吗
在python中,每次编辑都会创建一个新字符串(或者至少不能保证它不会分配一个新字符串)。我认为关注自己的堆栈(也就是一个由字符组成的数组,指针指向末尾)可以产生更好的代码。在python中有几种管理堆栈的方法,最常见的是列表,另一个好的选择是收藏.deque. 除非分析人员另有说明,否则我会选择更熟悉的列表。你知道吗
最后的比较方法可能看起来像
上面的代码有两个问题。首先,它几乎可以保证创建两个新字符串。第二个是它需要对字符串进行四次总的传递,每个输入字符串一次,每个清理过的字符串一次。你知道吗
这可以通过向后而不是向前改进。通过向后迭代,可以看到backspaces,并提前知道哪些字符将被删除(read-ignored或skipped)。我们一直这样做,直到出现不匹配,或者至少有一个字符串的字符用完为止。这种方法需要更多的簿记,但不需要额外的空间。它只使用两个指针跟踪每个字符串的当前进度,并使用一个计数器跟踪要忽略的字符数。下面给出的代码不是特别python的,它可以做得更好。如果你要用两台发电机和一台izipèu,你可以把所有的样板都去掉。你知道吗
编辑
下面是我为compare的上一个实现尝试的一些测试用例。你知道吗
相关问题 更多 >
编程相关推荐