0

我在 python 中有一些字符串，例如 :'I go to by everyday' 和'I go to school by bus everyday'and 。'you go to home by bus everyday'我想知道是否可以仅通过插入一些字符将第一个转换为另一个？如果是，请获取字符以及它们必须插入的位置！我用过difflib.SequenceMatcher，但在一些有重复单词的字符串中它不起作用！

4

4 回答 4

1

让我们重述这个问题，并假设我们正在检查 s1（例如“我每天去”）是否可以变成 s2（例如“我每天乘公共汽车上学”），只需插入。如果我们将字符串视为有序集合，这个问题就非常简单。本质上，我们是在询问 s1 是否是 s2 的子集。

为了解决这个问题，贪心算法就足够了（并且是最快的）。我们遍历 s1 中的每个字符，并尝试在 s2 中找到该字符的第一次出现。同时，我们保留一个缓冲区来保存我们在查找字符时遇到的所有不匹配字符，以及我们首先开始填充缓冲区的位置。当我们找到我们正在寻找的字符时，我们将缓冲区的位置和内容转储到一个占位符中。

当我们在 s2 之前到达 s1 的末尾时，这实际上意味着 s1 是 s2 的子集，我们返回占位符。否则 s1 不是 s2 的子集，并且不可能仅通过插入从 s1 形成 s2，因此我们返回 false。这个贪心算法需要 O(len(s1) + len(s2)) ，下面是它的代码：



# we are checking if we can make s2 from s1 just with inserts
def check(s1, s2):

    # indices for iterating through s1 and s2
    i1 = 0
    i2 = 0

    # dictionary to keep track of where to insert what
    inserts = dict()
    buffer = ""
    pos = 0

    while i1 < len(s1) and i2 < len(s2):
        if s1[i1] == s2[i2]:
            i1 += 1
            i2 += 1
            if buffer != "":
                inserts[pos] = buffer
                buffer = ""
            pos += 1
        else:
            buffer += s2[i2]
            i2 += 1

    # if possible return the what and where to insert, otherwise return false
    if i1 == len(s1):
        return inserts
    else:
        return False

于 2013-08-14T07:58:20.603 回答
0

有趣的问题。您可以使用正则表达式来检查。像这样的东西：

main = "I go to by everyday"
to_search = "I go to school by bus everyday"

import re
pattern = [chr for chr in main]
pattern = "(.*?)" + "(.*?)".join(pattern) + "(.*?)"
pattern = pattern.replace(' ', '\s{1}')
pattern = re.compile(pattern)

pattern.findall(to_search)

虽然它可能并不完美（不适用于必须转义的字符\，但我相信你可以调整它）。

请注意，您只是说inserts。因此，如果获取字符串I go to by everyday并在字符串中的字符之间放置任意数量的字符，我将得到我想要的。因此，将该字符串转换为以下正则表达式的想法：

(.*?)I(.*?)\s{1}(.*?)g(.*?)o(.*?)\s{1}(.*?)t(.*?)o(.*?)\s{1}(.*?)b(.*?)y(.*?)

请注意，空格已被\s{1}运算符替换，(.*?)基本上意味着“抓住所有并把它放在一个组中”。对于第一个字符串，您应该得到以下结果：

[('', '', '', '', '', '', '', '', 'school ', '', '', 'bus ', '', '', '', '', '', '', '', '')]

这将告诉您必须在原始字符串中的每个字符之前插入哪些字符串（加上最后一个字符）。

对于第二个字符串，您将收到一个空列表，因为初始字符串不能转换为它（缺少“I”字符）。

于 2013-08-14T06:44:21.043 回答
0

可以将第一个转换为第二个，但不能转换为第三个。例如：

words = sentence.split()
words.insert("school", 3)
words.insert("bus", 6)
sentence = ' '.join(words)

不能仅通过插入将第二个字符串转换为任何其他字符串，因为“I”需要替换为“you”。

于 2013-08-14T06:24:38.463 回答
0

您可以并行遍历两个字符串，为每个字符串维护一个索引。对于每个相等的字符，您增加两个索引 - 对于每个不相等的字符，您只需将索引增加到字符串中以进行测试：

def f(s, t):
  """Yields True if 's' can be transformed into 't' just by inserting characters,
  otherwise false
  """

  lenS = len(s)
  lenT = len(t)

  # 's' cannot possible get turned into 't' by just insertions if 't' is shorter.
  if lenS > lenT:
    return False

  # If both strings are the same length, let's treat 's' to be convertible to 't' if
  # they are equal (i.e. you can transform 's' to 't' using zero insertions). You
  # may want to return 'False' here.
  if lenS == lenT:
    return s == t

  idxS = 0
  for ch in t:
    if idxS == lenS:
      return True
    if s[idxS] == ch:
      idxS += 1

  return idxS == lenS

这让你

f('', 'I go to by everyday')                               # True
f('I go to by everyday', '')                               # False
f('I go to by everyday', 'I go to school by bus everyday') # True
f('I go to by everyday', 'you go to home by bus everyday') # False
于 2013-08-14T08:52:24.447 回答