要建设网站,泰安网红瑶瑶,网站空间ftp连接失败,公司网站建设技术方案模板本文首发于公众号「五分钟学算法」#xff0c;是图解 LeetCode 系列文章之一。个人网站#xff1a;https://www.cxyxiaowu.com题目来源于 LeetCode 第 125 号问题#xff1a;验证回文串。这道题目是 初级程序员 在面试的时候经常遇到的一道算法题#xff0c;而且面试官喜欢…本文首发于公众号「五分钟学算法」是图解 LeetCode 系列文章之一。 个人网站https://www.cxyxiaowu.com题目来源于 LeetCode 第 125 号问题验证回文串。这道题目是 初级程序员 在面试的时候经常遇到的一道算法题而且面试官喜欢面试者手写题目描述给定一个字符串验证它是否是回文串只考虑字母和数字字符可以忽略字母的大小写。说明本题中我们将空字符串定义为有效的回文串。示例 1:输入: A man, a plan, a canal: Panama
输出: true示例 2:输入: race a car
输出: false题目解析先理解一个概念所谓回文就是一个正读和反读都一样的字符串。先假设是验证单词 level 是否是回文字符串通过概念涉及到 正 与 反 那么很容易想到使用双指针从字符的开头和结尾处开始遍历整个字符串相同则继续向前寻找不同则直接返回 false。而这里与单独验证一个单词是否是回文字符串有所区别的是加入了 空格 与 非字母数字的字符但实际上的做法一样的一开始先建立两个指针left 和 right , 让它们分别从字符的开头和结尾处开始遍历整个字符串。如果遇到非字母数字的字符就跳过继续往下找直到找到下一个字母数字或者结束遍历如果遇到大写字母就将其转为小写。当左右指针都找到字母数字时可以进行比较的时候比较这两个字符如果相等则两个指针向它们的前进方向挪动然后继续比较下面两个分别找到的字母数字若不相等直接返回 false。动画描述代码实现注isLetterOrDigit 方法确定指定的字符是否为字母或数字。class Solution {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;}
}