首页 > 代码库 > Leetcode: Valid Palindrome
Leetcode: Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.For example,"A man, a plan, a canal: Panama" is a palindrome."race a car" is not a palindrome.Note:Have you consider that the string might be empty? This is a good question to ask during an interview.For the purpose of this problem, we define empty string as valid palindrome.
难度：79. 这道题是判断一个字符串是不是回文串。因为只是看一个字符串，算法还是比较简单，就是从两头出发，往中间走，进行两两匹配。这里面的小问题就是在这个题目要求中，只判断字母和数字类型的字符，其他字符直接跳过即可。因此我们要写一个函数判断他是不是合法字符，而且因为忽略大小写，我们在判断两个字符是不是相同的时候如果是大写，要转成相应的小写字母。这个算法从两边扫描，到中间相遇，只需要一次线性扫描，复杂度是O(n)，空间上是O(1)。
1 public class Solution { 2 public boolean isPalindrome(String s) { 3 if (s == null || s.length() == 0) { 4 return true; 5 } 6 int l = 0; 7 int r = s.length() - 1; 8 while (l < r) { 9 while (l<s.length() && !isValidChar(s.charAt(l))) {10 l++;11 }12 while (r>0 && !isValidChar(s.charAt(r))) {13 r--;14 }15 if (l < r) {16 if (isSame(s.charAt(l), s.charAt(r))) {17 l++;18 r--;19 }20 else return false;21 }22 }23 return true;24 }25 26 public boolean isValidChar(char c) {27 if ((c>=‘a‘ && c<=‘z‘) || (c>=‘A‘ && c<=‘Z‘) || (c>=‘0‘ && c<=‘9‘))28 return true;29 else return false;30 }31 32 public boolean isSame(char s1, char s2) {33 if (s1>=‘A‘ && s1<=‘Z‘) {34 s1 = (char)(s1 - ‘A‘ + ‘a‘);35 }36 if (s2>=‘A‘ && s2<=‘Z‘) {37 s2 = (char)(s2 - ‘A‘ + ‘a‘);38 }39 if (s1 == s2) {40 return true;41 }42 else return false;43 }44 }
Leetcode: Valid Palindrome
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。