0%

LeetCode题解5

发表于 更新于 分类于
本文字数： 3.6k 阅读时长 ≈ 3 分钟

LeetCode题解

第5题，最长回文子串

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

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”
输出: “bb”

原题如上，代码如下：

动态规划法：

python版本

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
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        bl = [[0 for i in range(n)]for i in range(n)]
        start = 0
        end = n
        for leng in range(1,n+1):
            for i in range(n-leng+1):
                if leng == 1:
                    bl[i][i] = 1
                    start = i
                    end = i + leng
                    continue
                if (leng == 2) & (s[i] == s[i + 1]):
                    bl[i][i + 1] = 1
                    start = i
                    end = i + leng
                    continue
                if (bl[i+1][i+leng-2] == 1) & (s[i] == s[i+leng-1]):
                    bl[i][i+leng-1] = 1 
                    start = i
                    end = i + leng
        return s[start:end]

18NKRP.png

c语言版本

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
char * longestPalindrome(char * s){
    int n = strlen(s);
    bool token[1000][1000] = {0}; //题目说明最大长度为1000
    int start = 0, end = n;
    for(int len = 1 ; len <= n ; len++){
        for(int i = 0 ; i <= n -len ; i++){
            if(len == 1){
                token[i][i] = 1;
                start = i;
                end = i + 1;
                continue;
            }
            if((len == 2) && (s[i] == s[i + 1])){
                token[i][i+1] = 1;
                start = i;
                end = i + 2;
                continue;
            }
            if((token[i+1][i+len-2] == 1) && (s[i] == s[i+len-1])){
                token[i][i+len-1] = 1;
                start = i;
                end = i + len;
            }
        }
    }
    s[end] = '\0';
    return &s[start];
}

18tvVJ.png

中心扩散法：

python版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def getstr(self,s,left,right):
        while left - 1 >= 0 and right < len(s):
            if s[left - 1] != s[right]:
                break
            left -= 1
            right += 1
        return s[left:right] 
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        result = ''
        n = len(s)
        for i in range(n):
            l = self.getstr(s,i,i+1)
            if len(l) >= len(result):
                result = l
            if i != n-1 and s[i] == s[i+1] :
                l = self.getstr(s,i,i+2)
                if len(l) >= len(result):
                    result = l          
        return result

10bXpq.png

c语言版本

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
char * longestPalindrome(char * s){
    int n = strlen(s), start = 0, end = 0;
    for(int i = 0; i < n; i++){ //奇数
        int left = i - 1, right = i + 1;
        while(left >= 0 && right < n && s[left] == s[right]){
            left--;
            right++;
        }
        if(right - left - 1 > end - start){
            start = left + 1;
            end = right;
        }
    }
    for(int i = 0; i < n - 1; i++){ //偶数
        if(s[i] == s[i + 1]){
            int left = i - 1, right = i + 2;
            while(left >= 0 && right < n && s[left] == s[right]){
                left--;
                right++;
            }
            if(right - left - 1 > end - start){
                start = left + 1;
                end = right;
            }
        }
    } 
    s[end] = '\0';
    return &s[start];
}

1NYoZT.png

解析：

​ 无论是动态规划法还是中心扩散法，理论上他们的时间复杂度都应该是O(n^2)​。

关于动态规划：

是有一个二维布尔数组bool_list[i][j]，若值为1，则表示字符串中 i 位到 j 位构成回文子串。

动态规划中首先遍历长度leng，每次再遍历字符串，观察是否具有长度为leng的回文子串。

1
2
for(int len = 1 ; len <= n ; len++) //leng从1开始
        for(int i = 0 ; i <= n -len ; i++) //每次遍历到字符串的n-leng位

其中boollist[i][j],若i = j，则恒为1，因为字符串始终具有长度为1的回文子串。

1
2
3
4
5
6
if(len == 1){
    token[i][i] = 1;
    start = i;
    end = i + 1;
   	continue;
}

同时回文子串也有奇数和偶数之分，奇数的回文字串中心为一个字符，而偶数的回文子串中心是两个相同的字符。所以当leng为2时要考虑偶数回文子串：

1
2
3
4
5
6
if((len == 2) && (s[i] == s[i + 1])){
    token[i][i+1] = 1;
	start = i;
 	end = i + 2;
	continue;
}

剩下就可以通解了：

1
2
3
4
5
if((token[i+1][i+len-2] == 1) && (s[i] == s[i+len-1])){
    token[i][i+len-1] = 1;
    start = i;
    end = i + len;
}

因为一个回文子串所具有的性质就是，每个元素和它的对称位置元素相同，且它俩中间包裹的子串也肯定时回文子串。

关于中心扩散：

其实，我们也可以这样找回文：

​ 遍历字符串每个元素，从每个元素出发，查看它两边的元素是否相等，相等则查看更外层两边元素是否相等，如此重复，直到不相等，则返回找到的奇数回文子串：

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0; i < n; i++){ //奇数
    int left = i - 1, right = i + 1;
    while(left >= 0 && right < n && s[left] == s[right]){
        left--;
        right++;
    }
    if(right - left - 1 > end - start){
        start = left + 1;
        end = right;
    }
}

​ 而偶数回文子串的寻找，和上述相似，只不过在最开始的中心元素是两个相等的元素，或者说是一条线为中心开始，向两边扩散：

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 0; i < n - 1; i++){ //偶数
    if(s[i] == s[i + 1]){
        int left = i - 1, right = i + 2;
        while(left >= 0 && right < n && s[left] == s[right]){
            left--;
            right++;
        }
        if(right - left - 1 > end - start){
            start = left + 1;
            end = right;
        }
    }
}

注意：要找到最大回文子串的话，可以在找到回文子串时和之前找到的最大回文子串长度比较，若大于则更新，若小于则不变。