Python 2.7 判断一个字符串的某个字谜是否是另一个字符串的子串

Question

编辑：发布我的最终解决方案，因为这是一个非常有用的线程，我想为其添加一些最终性。使用以下两个答案中的建议，我能够制定一个解决方案。我添加了一个辅助函数，在其中定义了一个字谜。这是我的最终解决方案：

def anagram(s1, s2):
    s1 = list(s1)
    s2 = list(s2)
    s1.sort()
    s2.sort()
    return s1 == s2

def Question1(t, s):
    t_len = len(t)
    s_len = len(s)
    t_sort = sorted(t)
    for start in range(s_len - t_len + 1):
        if anagram(s[start: start+t_len], t):
            return True
    return False

print Question1("app", "paple")

我正在练习一些技术面试问题，但遇到了以下问题：

Find whether an anagram of string t is a substring of s

我已经制定了以下两种代码变体，我认为解决这个问题的方法在于两者之间的交叉。我遇到的问题是无论输入如何，第一个代码总是打印 False.。第二种变体在某种程度上起作用。但是，它不能对单个字母进行排序。例如 t=jks s=jksd 将打印 True! 而 t=kjs s=jksd 将打印 False.

def Question1():
    # Define strings as raw user input.
    t = raw_input("Enter phrase t:")
    s = raw_input("Enter phrase s:")
    # Use the sorted function to find if t in s
    if sorted(t.lower()) in sorted(s.lower()):
        print("True!")
    else:
        print("False.")

Question1()

工作变体：

def Question1():
    # Define strings as raw user input.
    t = raw_input("Enter phrase t:")
    s = raw_input("Enter phrase s:")
    # use a loop to find if t is in s.
    if t.lower() in s.lower():
        print("True!")
    else:
        print("False.")

Question1()

我相信有一个介于这两者之间的解决方案，但我无法弄清楚如何在这种情况下使用 sorted。

Answer 1

我认为你的问题出在"substring"要求上。如果你排序，你就会破坏秩序。这意味着虽然您可以确定 string1 的变位词是 string2 的子字符串的变位词，但在您实际按顺序处理 string2 之前，您不会得到正确的答案。

我建议遍历 s2 中长度为 len(s1) 的所有子字符串。这是一个简单的 for 循环。获得子字符串后，您可以将它们（排序与排序）与 s1 进行比较，以确定是否存在 s1 的任何重新排列，从而产生 s2.[=16= 的连续子字符串]

即：

s1 = "jks"
s2 = "aksjd"

print('s1=',s1, ' s2=', s2)
for offset in range(len(s2) - len(s1) + 1):
    ss2 = s2[offset:offset+len(s1)]
    if sorted(ss2) == sorted(s1):
        print('{} is an anagram of {} at offset {} in {}'.format(ss2, s1, offset, s2))

Answer 2

您的方向非常正确。首先，请注意您第二次尝试没有循环。

问题是您不能简单地对 s 的 all 进行排序，然后在其中查找 sorted(t)。相反，您必须考虑 s 的每个 len(t) 大小的子字符串，并根据排序的 t 检查 that。考虑这个简单的例子：

t = "abd"
s = "abdc"

s 平凡地包含 t。但是，当你对它们进行排序时，你会得到字符串 abd 和 abcd，并且 in 比较失败.排序会妨碍其他字母。

相反，您需要以 t.

大小的块逐步执行 s

t_len = len(t)
s_len = len(s)
t_sort = sorted(t)
for start in range(s_len - t_len + 1):
   chunk = s[start:start+t_len]
   if t_sort == sorted(chunk):
       # SUCCESS!!

Python 2.7 判断一个字符串的某个字谜是否是另一个字符串的子串

Python 2.7 finding if some anagram of one string is a substring of another

python

python-2.7

boolean

anagram