Python - 确定一个词是否使用这种语言

Question

我在解决这个家庭作业问题时遇到了问题。如果有人可以给我任何提示或开始的东西，那就太好了!提前致谢!

鲍勃和乔决定创造一种新语言。他们语言中的单词仅由字母 A、B 和 C 组成。他们发明的第一个单词是 AB 和 C。然后他们决定所有其他单词的形式为 AuB 或 vCw，其中 u、v 和 w 都是以前发明的词。 (注意 v 和 w 可能是同一个词。)编写一个 in_language 函数，它使用字符串 s 并在 s 在语言中时产生 True，否则产生 False。

例子:

in_language('C') => True
in_language('AB') => True
in_language('ACB') => True
in_language('ABCAB') => True
in_language('ACBCABCAB') => True

in_language('') => False (empty string with length 0)
in_language('A') => False
in_language('A^BD%AB') => False
in_language('BCA') => False
in_language('ACBACB') => False

Answer 1

这是一个简单的递归算法:

1. 如果单词为空，返回False
2. 如果一个词是 AB 或 C 则返回 True
3. 如果一个单词以A开头，以B结尾，如果内部是一个有效的单词则返回True(递归)
4. else 对于单词中的每个字母C，如果左边部分和右边部分都是有效单词则返回True(递归)
5. 如果以上都不成立，则返回false

这是 SwankyLegg 要求的实现

def in_language(word):
    if word in ('AB', 'C'):
        return True
    if len(word) < 3: #The only valid words with 2 or less letters are AB and C
        return False
    if word[0] == 'A' and word[-1] == 'B' and in_language(word[1:-1]):
        return True
    else:
        for i, letter in enumerate(word):
            if letter == 'C' and in_language(word[:i]) and in_language(word[i+1:]):
                return True
    return False