leetcode 647. Palindromic Substrings（python）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode 647. Palindromic Substrings（python），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2458字，纯文字阅读大概需要4分钟。

内容图文

描述

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

The input string length won't exceed 1000.

解析

根据题意，暴力破解，直接用双重循环，将各种组合都判断一次，时间复杂度为 O(N^2)，空间复杂度为 O(1)。

解答

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        count = 0
        for i in range(len(s)):
            for j in range(i+1,len(s)+1):
                if s[i:j] == s[i:j][::-1]:
                    count += 1
        return count

运行结果

Runtime: 752 ms, faster than 9.08% of Python online submissions for Palindromic Substrings.
Memory Usage: 11.9 MB, less than 39.45% of Python online submissions for Palindromic Substrings.

解析

根据题意，另一种思路比较巧妙，在从左到右遍历字符串的同时，以每个字符为中心，向两边扩展开来判断各种可能成为回文数的组合，时间复杂度为 O(N^2)，空间复杂度为 O(1)。

解答

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        count = 0
        for i in xrange(len(s)):
            #自身是回文数
            count += 1
            #回文长度是奇数的情况
            left = i - 1
            right = i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
            #回文长度是偶数的情况
            left = i
            right = i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
        return count

运行结果

Runtime: 100 ms, faster than 75.24% of Python online submissions for Palindromic Substrings.
Memory Usage: 11.8 MB, less than 74.94% of Python online submissions for Palindromic Substrings.

解析

根据题意，再有一种思路就是动态规划，单个字符是回文；两个连续字符如果相等是回文；如果有3个以上的字符，需要两头相等并且去掉首尾之后依然是回文。时间复杂度为 O(N^2)，空间复杂度为 O(1)。

解答

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        N = len(s)
        count = 0
        dp = [[0]*N for _ in range(N)]
        for j in range(N):
            for i in range(j):
                dp[i][j] = (s[i]==s[j]) & (dp[i+1][j-1] | (j-i<2) ) 
                if dp[i][j]:
                        count += 1
            dp[j][j] = 1
            #自身是回文数
            count += 1
        return count

运行结果

Runtime: 320 ms, faster than 29.55% of Python online submissions for Palindromic Substrings.
Memory Usage: 19.5 MB, less than 18.12% of Python online submissions for Palindromic Substrings.

每日格言：常常是最终一把钥匙打开了门。

内容总结

以上是互联网集市为您收集整理的leetcode 647. Palindromic Substrings（python）全部内容，希望文章能够帮你解决leetcode 647. Palindromic Substrings（python）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端