【面试刷题-力扣经典】409最长回文串、647回文子串、5最长回文子串

川长思鸟来 2021-09-21 05:46 354阅读 0赞

### 409. 最长回文串 ###

**【题目】**

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

**【示例】**

输入:  
“abccccdd”

输出:  
7

解释:  
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

**【代码】**

package LeetCode;
    
    import java.util.*;
    
    public class LeetCode409 { 
        public int longestPalindrome(String s) { 
            Map<Character,Integer> map = new HashMap<>();
    
            int i,count,size;
    
    
            // 获得每个字符的个数
            for (i=0; i<s.length(); i++) { 
                count = 0;
                if (map.containsKey(s.charAt(i))) { 
                    count = map.get(s.charAt(i));
                }
                map.put(s.charAt(i),++count);
            }
    
            Iterator it = map.entrySet().iterator();
    
            // 记录出现次数为奇数的次数
            size = 0;
            while (it.hasNext()) { 
                Map.Entry<Character,Integer> entry = (Map.Entry<Character, Integer>) it.next();
                if (entry.getValue()%2!=0) { 
                    size++;
                }
            }
    
            if (size==0) return s.length();
            else return s.length()-size+1;
        }
    
        public static void main(String[] args) { 
            System.out.println(new LeetCode409().longestPalindrome("abccccdd"));
        }
    }

--------------------

### 647. 回文子串 ###

**【题目】**

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

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

**【示例】**

输入: “abc”  
输出: 3  
解释: 三个回文子串: “a”, “b”, “c”.

**【代码】**

class Solution { 
        /** * 考虑使用动态规划 * dp[x][y] 代表的是从x到y是回文子串 * dp[x][y] = dp[x+1][y-1]是回文子串，并且a[x]==a[y] * 边界：把回文1串和回文2串找到 * 这次的遍历是回文串的长度 **/
        public int countSubstrings(String s) { 
    
            if ("".equals(s) || s==null) return 0;
    
            int count,i,j,k;
            boolean[][] dp = new boolean[s.length()][s.length()];
    
            dp[0][0] = true;
            count = 1;
            for (i=1; i<s.length(); i++) { 
                dp[i][i] = true;
                count++;
                if (s.charAt(i-1)==s.charAt(i)) { 
                    dp[i-1][i]=true;
                    count++;
                }
            }
    
            // i代表的是回文串的长度
            for (i=3; i<=s.length(); i++) { 
                for (j=0; (j+i-1)<s.length(); j++) { 
                    k = j+i-1;
                    if (dp[j+1][k-1] && s.charAt(j)==s.charAt(k)) { 
                        dp[j][k] = true;
                        count++;
                    }
                }
            }
    
            return count;
    
        }
    }

--------------------

### 5. 最长回文子串 ###

**【题目】**

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

**【示例】**

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

**【思考】**

这道题目在上一道题目的基础上求解即可，都是寻找所有的回文子串，一个是求最长，一个是所有的个数。

**【代码】**

class Solution { 
        public String longestPalindrome(String s) { 
            if (s==null || s.length()==0) return "";
    
            int i,j,len,l,r,res,k;
            len = s.length();
            boolean[][] dp = new boolean[len][len];
    
            // 初始化边界
            dp[0][0] = true;
            l = r = 0;
            res = 1;
            for (i=1; i<len; i++) { 
                dp[i][i] = true;
                if (s.charAt(i-1) == s.charAt(i)) { 
                    dp[i-1][i] = true;
                    res = 2;
                    l = i-1;
                    r = i;
                }
            }
    
            for (i=3; i<=len; i++) { 
                for (j=0; (j+i-1)<len; j++) { 
                    k = j+i-1;
                    if (dp[j+1][k-1] && s.charAt(j)==s.charAt(k)) { 
                        dp[j][k] = true;
                        if (res < (k-j+1)) { 
                            res = k-j+1;
                            l = j;
                            r = k;
                        }
                    }
    
                }
            }
            return s.substring(l,r+1);
        }
    }

--------------------

**【Java 面试那点事】**

**这里致力于分享 Java 面试路上的各种知识，无论是技术还是经验，你需要的这里都有！**

**这里可以让你【快速了解 Java 相关知识】，并且【短时间在面试方面有跨越式提升】**

**面试路上，你不孤单！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/26c21cd96c3a409f8e994a0021dc35e9.png