文档章节

LeetCode:Valid Palindrome - 回文字符串

北风其凉
 北风其凉
发布于 2015/08/05 23:17
字数 723
阅读 410
收藏 1

1、题目名称

Valid Palindrome(回文字符串)

2、题目地址

https://leetcode.com/problems/valid-palindrome/

3、题目内容

英文:Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

中文:给出一个字符串,只考虑字母和数字,判断该字符串是否为回文字符串

例如:

"A man, a plan, a canal: Panama" 是一个回文字符串

"race a car" 不是一个回文字符串

4、题目分析

如果要判断一个字符串是否是回文字符串,可以两个变量,从两侧开始比较有效的字符是否相等。这里有效的字符是指 'a'-'z'、'A'-'Z'、'0'-'9' 这三个区间内的字符。

5、解题方法1

可以将字符串中有效的字符,写入一个链表,再将链表转化为数组,直接判断数组两侧对称位置的字符是否匹配。

实现的Java代码如下:

import java.util.LinkedList;

/**
 * 功能说明:LeetCode 125 - Valid Palindrome
 * 开发人员:Tsybius2014
 * 开发时间:2015年8月4日
 */
public class Solution {
    
    /**
     * 检测一个字符串是否是回文(忽略大小写,只考虑英文和数字)
     * @param s 被检测字符串
     * @return
     */
    public boolean isPalindrome(String s) {
        
        if (s == null) {
            return false;
        }
        
        if (s.trim().isEmpty()) {
            return true;
        }
        
        //将有效字符选出并存入链表
        LinkedList<Character> linkedList = new LinkedList<Character>();
        for (char ch : s.toCharArray()) {
            if ((ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) {
                linkedList.add(ch);
            } else if (ch >= 'A' && ch <= 'Z') {
                linkedList.add((char)(ch + 'a' - 'A'));
            }
        }
        if (linkedList.size() <= 1) {
            return true;
        }

        //将链表转换为数组比较
        Object[] array = linkedList.toArray();
        for (int i = 0; i <= array.length / 2; i++) {
            if (!array[i].equals(array[array.length - 1 - i])) {
                return false;
            }
        }
        
        return true;
    }
}

6、解题方法2

选择两个数字i和j,直接从字符串的首和尾开始循环,直到i>=j为止。如果出现两侧对应字符不匹配的情况,则直接判定此字符串不是回文字符串。全部字符考察完毕后,如果未发现对应位置字符不匹配的情况,则认为此字符串是回文字符串。

实现的Java代码如下:

import java.util.LinkedList;

/**
 * 功能说明:LeetCode 125 - Valid Palindrome
 * 开发人员:Tsybius2014
 * 开发时间:2015年8月4日
 */
public class Solution {
    
    /**
     * 检测一个字符串是否是回文(忽略大小写,只考虑英文和数字)
     * @param s 被检测字符串
     * @return
     */
    public boolean isPalindrome(String s) {

        if (s == null) {
            return false;
        }
        
        if (s.trim().isEmpty()) {
            return true;
        }
        
        int i = 0;
        int j = s.length() - 1;
        
        int chLeft; //左侧字符
        int chRight; //右侧字符
        while (i < j) {
            
            chLeft = s.charAt(i);
            chRight = s.charAt(j);

            //既非英文也非数字的字符直接忽略
            if (!(chLeft >= 'A' && chLeft <= 'Z') &&
                !(chLeft >= 'a' && chLeft <= 'z') &&
                !(chLeft >= '0' && chLeft <= '9')) {
                i++;
                continue;
            }

            if (!(chRight >= 'A' && chRight <= 'Z') &&
                !(chRight >= 'a' && chRight <= 'z') &&
                !(chRight >= '0' && chRight <= '9')) {
                j--;
                continue;
            }
                        
            //大写英文字母转成小写
            if (chLeft >= 'A' && chLeft <= 'Z') {
                chLeft = chLeft + 'a' - 'A';
            }
            
            if (chRight >= 'A' && chRight <= 'Z') {
                chRight = chRight + 'a' - 'A';
            }
            
            //比较字符
            if (chLeft != chRight) {
                return false;
            } else {
                i++;
                j--;
            }
        }
        
        return true;
    }
}

END

© 著作权归作者所有

北风其凉

北风其凉

粉丝 123
博文 497
码字总数 462305
作品 4
朝阳
程序员
私信 提问
加载中

评论(0)

每日算法之LeetCode 125:Valid Palindrome(有效回文)

LeetCode 125:Valid Palindrome(有效回文) Q:Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Note: For the purpose ......

錦小白
2018/08/18
0
0
[LeetCode] Valid Palindrome II 验证回文字符串之二

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome. Example 1: Input: "aba"Output: True Example 2: Input: "abca"Output:......

机器的心脏
2017/12/06
0
0
leetCode 125. Valid Palindrome 字符串

125. Valid Palindrome Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, is a palindrome. is not a palind......

wbf961127
2017/11/13
0
0
leetcode-9 Palindrome Number 回文

layout: post title: "leetcode-9 Palindrome Number 回文" tags: - leetcode - python - algorithm - Palindrome 回文 Palindrome Number 判断一个整数是否是回文数。回文数是指正序(从左向......

sz88888
2019/04/10
0
0
LeetCode-回文的判断——D14【简单】

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/qq33414271/article/details/99493734 题目描述 Given a string, de...

土豆洋芋山药蛋
2019/08/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

5G改变物联网解决方案的6种方式

简介: 5G的实施将促进更顺畅、更强大和多层网络的发展。这将如何影响物联网解决方案领域?首先,它将加速智慧城市的曙光。 为什么5G是最近记忆中最迫切期待的技术之一,为什么它在地缘政治上...

osc_lyz4aksj
2分钟前
0
0
归一化激活层的进化:谷歌Quoc Le等人利用AutoML 技术发现新型ML模块 - 知乎

最近,谷歌大脑团队和 DeepMind 合作发布了一篇论文,利用 AutoML 技术实现了归一化激活层的进化,找出了 BatchNorm-ReLU 的替代方案 EvoNorms,在 ImageNet 上获得 77.8% 的准确率,超越 BN...

osc_l9a67e5j
3分钟前
0
0
淘宝运营之SEO的三大误区

哈喽大家好,我是大毛!继上一集我说到关于淘宝搜索并提到了SEO,那么我今天再来补充一下,关于淘宝SEO的三大误区。有人说,价格越低越能找到我家的宝贝,这种思想就是不行滴伙计!把价格放低...

osc_k3vwonkw
4分钟前
0
0
多用户商城系统开发要注意什么?

  商城系统开发要注意什么?随着互联网发展,电子商务空前繁荣,以淘宝京东为代表的商城系统大受追捧,同时也方便了人们生活。那么商城系统开发要注意什么呢?大商创B2B2C多用户商城系统开...

大商创多用户商城
4分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部