0%

机试-回文子串相关

发表于 更新于 阅读次数： Valine：
本文字数： 451 阅读时长 ≈ 1 分钟

回文子串

例：给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        length = len(s) 
        result = 0
        for i in range(length):
            for j in range(i+1,length+1): #这里注意循环的范围为range(i+1,length+1)    
                if s[i:j]==s[i:j][::-1]:
                    result += 1
        
        return result

最长回文子串

​ 最长回文子串也是回文串中常见的一中题目，下面是例题

例：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

思路一：Manacher算法

​ 首先先将字符串首尾以及字符和字符之间采用”#“进行补齐，补齐后的字符串总长度2n+1(n为原始字符串长度)。然后从第一个非#字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def get_length(string, index):
            # 循环求出index为中心的最长回文字串
            length = 0
            seq = ""
            if string[index]!="#":
                seq = string[index]
                length = 1
            string_len = len(string)
            for i in range(1,index+1):
                if index+i<string_len and string[index-i]==string[index+i]:
                    # print(string[index-i],seq+string[index+i])
                    if string[index-i]!="#":
                        length +=2
                        seq = string[index-i]+seq+string[index+i]
                else:
                    break
            return length,seq
        
        s_list = [i for i in s]
        string = "#"+"#".join(s)+"#"
        
        length = len(string)
        max_length = 0
        max_seq = ""
        
        for index in range(0,length):
            # print("====")
            tmp_len,tmp_seq = get_length(string,index)
            # print(tmp_len,tmp_seq)
            if tmp_len>max_length:
                max_length = tmp_len
                max_seq = tmp_seq
            
        return max_seq

思路二：动态规划

​ 这里的动态规划的核心思路就是从头开始向后进行遍历，每次想看头尾同时加入比最大之前最大回文子串的长多+1字符串是不是回文子串(注意但是首部索引不能超过0)，如果是则记录起始节点start，max_len的值+2；否则判断只在尾部进行字符串加1的字符串时不是回文子串（这里之说以不必尝试在头部加1，因为再从头开始遍历的过程中已经尝试了头部加1），如果是记录start节点，max_len的值+2

​ f(x+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        length = len(s)
        max_len = 0
        start = 0
        
        for i in range(length):
            if i-max_len>=1 and s[i-max_len-1:i+1]==s[i-max_len-1:i+1][::-1]:
                start = i-max_len-1
                max_len += 2
            elif i-max_len>=0 and s[i-max_len:i+1]==s[i-max_len:i+1][::-1]:
                start = i-max_len
                max_len += 1
            
        return s[start:start+max_len]

最长回文子序列516

​

z