Skip to content

Latest commit

 

History

History
214 lines (149 loc) · 6.12 KB

04.回文字符串.md

File metadata and controls

214 lines (149 loc) · 6.12 KB
Raw

目录介绍

  • 01.题目要求
  • 02.最长回文串
  • 03.验证回文串
  • 04.最长回文子串

好消息

  • 博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！所有博客陆续更新到GitHub上！
  • 链接地址：https://github.com/yangchong211/YCBlogs
  • 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

01.题目要求

  • 问题如下所示：
    • 回文串：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
  • 示例 : 
    1234321    level    noon 等都是回文字符串

02.最长回文串

  • 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如"Aa"不能当做一个回文字符串。注意:假设字符串的长度不会超过 1010。 示例 1: 
    输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
  • 可以构成回文串的两种情况：
    • 字符出现次数为双数的组合
    • 字符出现次数为双数的组合+一个只出现一次的字符
  • 代码实现
    • 统计字符出现的次数即可，双数才能构成回文。因为允许中间一个数单独出现，比如“abcba”，所以如果最后有字母落单，总长度可以加 1。首先将字符串转变为字符数组。然后遍历该数组，判断对应字符是否在hashset中，如果不在就加进去，如果在就让count++，然后移除该字符！这样就能找到出现次数为双数的字符个数。
    public  int LengthPalindrome(String s) {
    if (s.length() == 0){
        return 0;
    }
    // 用于存放字符
    HashSet<Character> hashSet = new HashSet<>();
    char[] chars = s.toCharArray();
    int count = 0;
    for (int i = 0; i < chars.length; i++) {
        // 如果hashSet没有该字符就保存进去
        if (!hashSet.contains(chars[i])) {
            hashSet.add(chars[i]);
        } else {
            // 如果有,就让count++（说明找到了一个成对的字符），然后把该字符移除
            hashSet.remove(chars[i]);
            count++;
        }
    }
    return hashSet.isEmpty() ? count * 2 : count * 2 + 1;
}

03.验证回文串

  • 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。
    • 示例 1:
    输入: "A man, a plan, a canal: Panama"
输出: true
    • 示例 2:
    输入: "race a car"
输出: false
  • 代码如下所示 
    public  boolean IsPalindrome(String s) {
    if (s.length() == 0){
        return true;
    }
    int l = 0, r = s.length() - 1;
    while (l < r) {
        // 从头和尾开始向中间遍历
        // 字符不是字母和数字的情况
        if (!Character.isLetterOrDigit(s.charAt(l))) {
            l++;
        } else if (!Character.isLetterOrDigit(s.charAt(r))) {
            // 字符不是字母和数字的情况
            r--;
        } else {
            // 判断二者是否相等
            if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
                return false;
            l++;
            r--;
        }
    }
    return true;
}

04.最长回文子串

  • 最长回文子串 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
    • 示例 1：
    输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
    • 示例 2：
    输入: "cbbd"
输出: "bb"
  • 代码如下所示 
    private int index, len;
public String LongestPalindrome(String s) {
    if (s.length() < 2){
        return s;
    }
    for (int i = 0; i < s.length() - 1; i++) {
        PalindromeHelper(s, i, i);
        PalindromeHelper(s, i, i + 1);
    }
    return s.substring(index, index + len);
}

public void PalindromeHelper(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    if (len < r - l - 1) {
        index = l + 1;
        len = r - l - 1;
    }
}

其他内容

01.关于博客汇总链接

02.关于我的博客