最长回文子串

发表于 | 分类于 ， ， |

​ 給一个字符串s，找到s中的最长的回文子串

最长回文子串和回文子串

5. 最长回文子串

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
class Solution {
public:
    //定义一个函数来寻找最长回文串
    string palindrome(string s, int l, int r) {
    // 防止索引越界
    while (l >=0 && r < s.size() && s[l] == s[r]) {
        // 双指针，向两边展开
        l--; 
        r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substr(l+1, r-l-1);
    }

    string longestPalindrome(string s) {
    string res;
    for (int i = 0; i < s.size(); i++) {
        // 以 s[i] 为中心的最长回文子串
        string s1 = palindrome(s, i, i);
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        string s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.size() > s1.size() ? res : s1;
        res = res.size() > s2.size() ? res : s2;
    }
    return res;
    } 
};
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
func longestPalindrome(s string) string {
    res := ""
    for i := 0; i < len(s); i++ {
        // 以 s[i] 为中心的最长回文子串
        s1 := palindrome(s, i, i)
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        s2 := palindrome(s, i, i+1)
        // res = longest(res, s1, s2)
        if len(res) < len(s1) {
            res = s1
        }
        if len(res) < len(s2) {
            res = s2
        }
    }
    return res
}

// 定义一个函数来寻找最长回文串
func palindrome(s string, l int, r int) string {
    // 防止索引越界
    for l >= 0 && r < len(s) && s[l] == s[r] {
        // 双指针，向两边展开
        l--
        r++
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s[l+1 : r]
}

时间复杂度：O(N^2^)

空间复杂度：O(1)

647. 回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countSubstrings(string s) {
        int result=0;
        for(int i=0; i<s.size(); i++){
            int a=Substring(s,i,i);
            int b=Substring(s,i,i+1);
            result += a+b;
        }
        return result;
    }

    int Substring(string s, int left, int right){
        int result=0;
        while(left>=0 && right<s.size() && s[left]==s[right]){
            left--;
            right++;
            result++;
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func countSubstrings(s string) int {
    result := 0
    for i := 0; i < len(s); i++ {
        a := substring(s, i, i)
        b := substring(s, i, i+1)
        result += a + b
    }
    return result
}

func substring(s string, left int, right int) int {
    result := 0
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
        result++
    }
    return result
}

时间复杂度：O(N^2^)

空间复杂度：O(1)

125. 验证回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isPalindrome(string s) {
        //双指针
        string res;
        for(char ch : s){
            if(isalnum(ch)){  //是否是字母和数字
                res += tolower(ch); //tolower()将大写转换成小写
            }
        }
        int n=res.size();
        int left = 0;
        int right = n-1;
        while(left<right){
            if(res[left]!=res[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};
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
func isPalindrome(s string) bool {
    // 双指针
    res := []rune{}
    for _, ch := range s {
        if isAlnum(ch) { // 是否是字母和数字
            res = append(res, toLower(ch)) // toLower()将大写转换成小写
        }
    }
    n := len(res)
    left := 0
    right := n - 1
    for left < right {
        if res[left] != res[right] {
            return false
        }
        left++
        right--
    }
    return true
}

func isAlnum(ch rune) bool {
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9')
}

func toLower(ch rune) rune {
    if ch >= 'A' && ch <= 'Z' {
        return ch + ('a' - 'A')
    }
    return ch
}
-------------本文结束 感谢阅读-------------
0%