算法@LeetCode:Valid Palindrome

Log

• 【170808】完成 01 版（Python）
• 【170808】完成 02 版（Python）

题目

Valid Palindrome

【题目类型备注】

双指针，字符串

提交

01

【语言】

Python

【时间】

170808

【思路】

1. 把所有字母或数字取出到列表中
2. 头指针指向列表开头，尾指针指向列表尾部
3. 每一轮，比较两根指针指向的字符是否相等；若不等，说明肯定不是回文数；若相等，头指针前进一步，尾指针后退一步，继续循环
4. 这里利用了 Python 的列表做了一点小技巧，例如 slices 和 enumerate

【代码】

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) <= 1:
            return True
        ts = [i.lower() for i in s if i.isalnum()]
        if len(ts) % 2 == 1:
            mid = len(ts)//2
        else:
            mid = len(ts)//2-1
        for i,val in enumerate(ts[-1:mid:-1]):
            if ts[i] != val:
                return False
            
        return True

【结果】

运行时：66 ms

报告链接：https://leetcode.com/submissions/detail/113017828/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 86.98 % of python submissions.

02

【语言】

Python

【时间】

170808

【思路】

与 01 版思路一致，不过没有再利用 slices 和 enumerate 而直接实现。发现时间差不多。

【代码】

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) <= 1:
            return True
        ts = [i.lower() for i in s if i.isalnum()]
        mid = len(ts)//2
        j = len(ts)-1
        for i in range(mid):
            if ts[i] != ts[j]:
                return False
            else:
                j -= 1
            
        return True

【结果】

运行时：65 ms

报告链接：https://leetcode.com/submissions/detail/113018541/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 88.79 % of python submissions

00

参考解法：

扫视了三种参考解，并没有比我更优

自己实现一遍最优解：

• [language]。。。