String-mainipulation6

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/longest-palindromic-substring/]

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

示例 1：

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

示例 2：

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

算法描述

​ 暴力法，遍历字符串，每次向两端扩展，注意边界条件，如果左右的单词长度相同继续执行，如果长度大于之前的长度，更新最长的字符串，直到遍历完字符串，返回最长回文串

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
class Solution {
public:
    string longestPalindrome(string s) {
        int res =0;
      string str;
      for(int i=0;i<s.size();i++){
        for(int j=0;i-j>=0&&i+j<s.size();j++)
          if(s[i-j]==s[i+j])
          {
            if(j*2+1>res){
              res = j*2+1;
              str = s.substr(i-j,j*2+1);
            }
          }
          else break;
          for(int j=i,k=i+1;j>=0&&k<s.size();j--,k++)
            if(s[j]==s[k]){
              if(k-j+1>res){
                res = k-j+1;
                str = s.substr(j,k-j+1);
              }
            }
           else break;
      }
      return str;
    }
};

Java代码

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 {
    public String longestPalindrome(String s) {
        int res = 0;
        String str="";
        for(int i=0;i<s.length();i++){
            for(int j=0;i-j>=0&&i+j<s.length();j++){
              if(s.charAt(i-j)==s.charAt(i+j)){
                if(j*2+1>res){
                  res = j*2+1;
                  str = s.substring(i-j,i+j+1);
                }
              }
              else break;
            }
          for(int j=i,k=i+1;j>=0&&k<s.length();j--,k++){
            if(s.charAt(j)==s.charAt(k)){
              if(k-j+1>res){
                res = k-j+1;
                str = s.substring(j,k+1);
              }
            }
            else break;
          }
        }
      return str;
    }
}