算法题-动态规划类型-最长回字符长

如题

何为回文

正序和倒叙相同即为回文

如 上海自来水来自海上

思路

因为要获得最长回文第一想到的是 获得每一种字符组合 即双for o(n2)复杂度

如下代码

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
public static  String longestPalindrome(String s)
   {
       String result;
       char[] ss=s.toCharArray();

       String twstr="";
       int k=0;
       for (int i=0;i<ss.length;i++)
       {
           //清空判断字符串
           result="";
           //获得每种字符组合
           if(i!=0) k+=1;
           for (int j=k;j<ss.length;j++){
               //拼接字符
               result+=ss[j];
               //判断同文
               if(result.equals(new StringBuffer(result).reverse().toString()))
               {
                   if(result.length()>twstr.length())
                   {
                      twstr=result;
                   }
               }
           }
       }
       return twstr;
   }

但是提交时提示时间过长….. 操

注意到一个规定你可以假设 s 的最大长度为 1000。

所以我这种暴力解法并不能提交成功;

第一种想法可能是像提示说的一样 将复杂度控制再 o(n)

第二种想法是 优化判断同文的语句if(result.equals(new StringBuffer(result).reverse().toString())) ,或者是说更改判断的方式

暴力题解答案

1 当字符长度为1时 最长回字符串为 s

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
35
36
public String longestPalindrome(String s) {
           int len = s.length();
           if (len < 2) {
               return s;
           }

           int maxLen = 1;
           int begin = 0;
           // s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组
           char[] charArray = s.toCharArray();

           // 枚举所有长度大于 1 的子串 charArray[i..j]
           for (int i = 0; i < len - 1; i++) {
               for (int j = i + 1; j < len; j++) {
                   if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
                       maxLen = j - i + 1;
                       begin = i;
                   }
               }
           }
           return s.substring(begin, begin + maxLen);
       }

       /**
        * 验证子串 s[left..right] 是否为回文串
        */
       private boolean validPalindromic(char[] charArray, int left, int right) {
           while (left < right) {
               if (charArray[left] != charArray[right]) {
                   return false;
               }
               left++;
               right--;
           }
           return true;
       }

动态规划还是看不太明白 自行查看把，，