回文实现.迭代和递归

Question

当面试官想确认我的回文是否"Taco！Cat!“时，我被问到这个回文问题。是回文。在本例中，我的回文实现需要处理复杂的示例，如空格、标点符号和混合字母大小写is_palindrome('Taco? Cat.')返回True。

def ascii_letters(text):
    #Helper method, it return true if all characters in the string are alphabetic
    # (if the string is an uppercase or lowercase letter from A to Z)
    # otherwise it will return False (the string contains any non-letter character)  
    string.ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
    string.ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    string.ascii_letters = string.ascii_lowercase + string.ascii_uppercase
    for index in text:
        if index in string.ascii_letters:
            return True
    return False
def is_palindrome_iterative(text):
    # implement the is_palindrome function iteratively here
    # to verify that my iterative implementation, must pass all tests    
    # First, set up the first_index and
    # last_index as the length of array -1  
    # Inside each iteration, compared the 2 pointers, and see if it's a palindrome    
    # to handle the different casing and punctuation: 
    # Called the helper function checks if index is ascii_letters or alphabetic
    first_index = 0
    last_index = len(text) - 1

    # checking the valid condition for the range
    while(first_index <= last_index):

        left = text[first_index]
        right = text[last_index]
        while not ascii_letters(left):
            first_index += 1
            if first_index > len(text) - 1:
                return True
        # check if the first pointer is not alphabetic or ascii_letters
        while not ascii_letters(right):
            last_index -= 1
            if last_index < 0:
                return True

        # if the pointer are not the same, return false
        if(left.lower() != right.lower()):
            return False
        first_index += 1
        last_index -= 1
    return True

def is_palindrome_recursive(text, first_index=None, last_index=None):
    # implement the is_palindrome function recursively here
    # to verify that your iterative implementation passes all tests
    # First, we have the first_index and last_index as None 
    # set the index for the 2 pointer
    # Inside the recursion, compared the 2 pointers, which check if it's a palindrome 
    # return fales   
    # to handle the different casing and punctuation: 
    # Called the helper function checks if index is ascii_letters or alphabetic
    if first_index is None or last_index is None:
        first_index = 0
        last_index = len(text) - 1
    # Base Cases
    if first_index >= last_index:
        return True
    # Check letters
    left = text[first_index]
    right = text[last_index]
    update_left = first_index + 1
    update_right = last_index - 1
    # check if the left pointer is not alphabetic or ascii_letters
    # if not, update the left pointer
    if not ascii_letters(left):
        return is_palindrome_recursive(text, update_left, last_index)
    # check if the right pointer is not alphabetic or ascii_letters
    # If not, update the right pointer
    if not ascii_letters(right):
        return is_palindrome_recursive(text, first_index, update_right)

    # Check if the left and right pointers are not the same
    # Not same, return false
    if(left.lower() != right.lower()):
        return False

    return is_palindrome_recursive(text, update_left, update_right)

我包括我的代码通过的所有测试用例：

#!python

from palindromes import is_palindrome
import unittest


class PalindromesTest(unittest.TestCase):

    def test_is_palindrome_with_whitespace_and_mixed_casing(self):
        # palindromes with whitespace and mixed letter casing
        assert is_palindrome('B b') is True
        assert is_palindrome('No On') is True
        assert is_palindrome('Dog God') is True
        assert is_palindrome('Taco Cat') is True
        assert is_palindrome('Race Car') is True
        assert is_palindrome('Race Fast Safe Car') is True

    def test_is_palindrome_with_whitespace_and_punctuation(self):
        # palindromes with whitespace and punctuation
        assert is_palindrome('B-B') is True
        assert is_palindrome('no, on!') is True
        assert is_palindrome('dog god?') is True
        assert is_palindrome('taco? cat.') is True
        assert is_palindrome('race-car!!!') is True
        assert is_palindrome('race fast, safe car...') is True

    def test_is_palindrome_with_mixed_casing_and_punctuation(self):
        # palindromes with whitespace, punctuation and mixed letter casing
        assert is_palindrome('No, On!') is True
        assert is_palindrome('Dog God?') is True
        assert is_palindrome('Taco? Cat.') is True
        assert is_palindrome('Race-Car!!!') is True
        assert is_palindrome('Race Fast, Safe Car...') is True
        assert is_palindrome('Was it a car or a cat I saw?') is True
        assert is_palindrome("Go hang a salami, I'm a lasagna hog.") is True
        assert is_palindrome('A man, a plan, a canal - Panama!') is True

    def test_is_palindrome_with_non_palindromic_strings(self):
        # examples of non-palindromic strings that should be rejected
        assert is_palindrome('AB') is False  # even length
        assert is_palindrome('ABC') is False  # odd length
        assert is_palindrome('AAB') is False
        assert is_palindrome('AABB') is False
        assert is_palindrome('AAABB') is False
        assert is_palindrome('AAABBB') is False
        assert is_palindrome('ABCZBA') is False
        assert is_palindrome('ABCCZA') is False
        assert is_palindrome('ABCCBZ') is False
        assert is_palindrome('ABCDZCBA') is False
        assert is_palindrome('ABCDDZBA') is False
        assert is_palindrome('ABCDDCZA') is False
        assert is_palindrome('ABCDDCBZ') is False
        assert is_palindrome('AAAAZAAA') is False
        assert is_palindrome('AAAAAAAZ') is False


if __name__ == '__main__':
    unittest.main()

Answer 1

可以改进的

内容：

• 包括import string (您使用它，但目前没有问题)
• 控制分离。不要让is_palindrome_iter和is_palindrome_recursive做标点符号删除。如果您想检查区分大小写的回文怎么办？
• 您使用的是string.ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'，但string.ascii_lowercase已经使用了。因此，这一行完全没有必要。
• 不要将块引号用作文档字符串！，而是使用实际的文档串
• 可以在递归函数中使用string切片。
• 当然，处理回文的最简单方法就是检查text == text[::-1]是否

代码更改，加上一些额外的

import string
import timeit

def is_palindrome_iter(text):
    """Returns True if palindrome
    This function hadles it iteravely"""

    text = remove_punctuation_and_lower(text)
    first_index, last_index = 0, len(text) - 1

    while(first_index <= last_index):
        if(text[first_index] != text[last_index]):
            return False

        first_index += 1
        last_index -= 1

    return True

def is_palindrome_rec(text):
    """Returns True if palindrome
    This function hadles it recursively"""

    if len(text) <= 1:
        return True

    if text[0] != text[-1]:
        return False

    return is_palindrome_recursive(text[1:-1])


def remove_punctuation_and_lower(text):
    """"Removes punctuation and lower the text"""
    return ''.join([i for i in text.lower() if i in string.ascii_letters])

def is_palindrome(text):
    """Simplest way to check for a palindrome"""
    text = remove_punctuation_and_lower(text)
    return text==text[::-1]

def palindrome_recursive(text):
    """Strip the punctuation adn check for recursive palindrome"""
    text = remove_punctuation_and_lower(text)
    return is_palindrome_rec(text)

定时

根据要求，与我的回文功能相比，您的回文功能的时间安排

def timing():
    setup = """s = 'A man, a plan, a canal - Panama!'
from __main__ import is_palindrome_iterative, is_palindrome_iter, is_palindrome, palindrome_recursive, is_palindrome_recursive"""
    print("Your iter: {}".format(min(timeit.Timer('is_palindrome_iterative(s)', setup=setup).repeat(7, 1000))))
    print("My iterative: {}\n".format(min(timeit.Timer('is_palindrome_iter(s)', setup=setup).repeat(7, 1000))))
    print("Your recursive: {}".format(min(timeit.Timer('is_palindrome_recursive(s)', setup=setup).repeat(7, 1000))))
    print("My recursive: {}\n".format(min(timeit.Timer('palindrome_recursive(s)', setup=setup).repeat(7, 1000))))
    print("Shortest: {}".format(min(timeit.Timer('is_palindrome(s)', setup=setup).repeat(7, 1000))))

其结果是：

Your iter: 0.023102631285895847
My iterative: 0.006382375491678111

Your recursive: 0.03150451902264695
My recursive: 0.021585517111614272

Shortest: 0.004582702402422756

正如您所看到的，与您的解决方案相比，我的解决方案更快，因此我们可以假设它在性能方面更好。如果你真的想拥有最快的解决方案，那么text == text[::-1]就赢了。这是因为，字符串比较将使用编译的C实现。而不是python循环，这个循环要慢得多。