如何使用递归来确定字符是否在字符串中？

Question

不管函数的第二个参数是否包含在第二个函数中。例如：

def recurseString(full, inclusive):
    ...............

基于此，我将采取以下措施：

^{pr2}$

这将返回“True”，而类似于：

recurseString('stan','xun')

会返回“False”

我对python比较陌生，所以这很令人困惑。有什么办法解决这个问题吗？在

Answer 1

即使inclusive中有重复的字母，但在full中只有一个，也会返回True：

def recurseString(full, inclusive):
    if not inclusive:
        return True
    return inclusive[0] in full and recurseString(full, inclusive[1:])

>>> print recurseString('jack','kkkcccjjj')
True

以下要求full包含相同数量的重复字母-如果inclusive有三个k，full必须有三个k：

^{pr2}$

使用index方法似乎是作弊

def foo(full, inclusive, first_call = True):
    if first_call:
        full, inclusive = map(sorted, (full, inclusive))
    if not full and inclusive:
        return False
    if not inclusive:
        return True
    if inclusive[0] == full[0]:
        inclusive = inclusive[1:]
    return foo(full[1:], inclusive, False)


assert not foo('','kkkcccjjj')
assert not  foo('sun','xun')
assert not  foo('jack','kkkcccjjj')
assert foo('s', 's')
assert foo('jckackjkjc','kkkcccjjj')
assert foo('','')
assert foo('a','')

Answer 2

我猜你在找。。。在

In [51]: def recurseString(a,b):
   ....:     if b == '': return True
   ....:     else:
   ....:         if len(b) == 1: return b in a
   ....:         else: return (b[0] in a) and recurseString(a, b[1:])
   ....:

In [52]: recurseString('jack', 'kjc')
Out[52]: True

In [53]: recurseString('stan', 'xun')
Out[53]: False

但是，不需要递归。使用all可以更好地解决这一问题，如下所示：

^{pr2}$

更像Python。在

也可以使用reduce，它的功能更强大，但可读性较差，因为Python有更好的处理方法。在

In [60]: reduce(lambda x,y: (x and (y in 'jack'))  , 'kjc', True)
Out[60]: True

最后，如果不使用set符号，这是不完整的：

In [65]: (set('kjc') - set('jack')) == set()
Out[65]: True

所以正如您所看到的，递归版本最不适合这个问题！在

Answer 3

要递归地考虑任何问题，您必须将其分为基本情况（有时是多个基本情况）和递归情况（有时是多个递归情况）。在

我假设“included by”意味着“在inclusive中的每个字符也在full中，事实上，出现在inclusiveN次中的每个字符也至少在full中。在

所以，如果inclusive是空的，那么它是空的。在

但是如果full为空，inclusive不是，则为False。在

否则，如果full的第一个字符是inclusive，则当full[1:]包含{}减去该字符时，它是真的。在

否则，如果full[1:]包含inclusive，则为真。在

现在你只需要把它翻译成代码。在

如果不需要处理重复字符，可以通过测试inclusive[0]并在inclusive[1:]上递归而不是在full[1:]上递归来简化这一过程。在