Valid Palindrome - LeetCode
Valid Palindrome -- LeetCode
原题链接: http://oj.leetcode.com/problems/valid-palindrome/
这道题是判断一个字符串是不是回文串。因为只是看一个字符串,算法还是比较简单,就是从两头出发,往中间走,进行两两匹配。这里面的小问题就是在这个题目要求中,只判断字母和数字类型的字符,其他字符直接跳过即可。因此我们要写一个函数判断他是不是合法字符,而且因为忽略大小写,我们在判断两个字符是不是相同的时候如果是大写,要转成相应的小写字母。这个算法从两边扫描,到中间相遇,只需要一次线性扫描,复杂度是O(n),空间上是O(1)。代码如下:
原题链接: http://oj.leetcode.com/problems/valid-palindrome/
这道题是判断一个字符串是不是回文串。因为只是看一个字符串,算法还是比较简单,就是从两头出发,往中间走,进行两两匹配。这里面的小问题就是在这个题目要求中,只判断字母和数字类型的字符,其他字符直接跳过即可。因此我们要写一个函数判断他是不是合法字符,而且因为忽略大小写,我们在判断两个字符是不是相同的时候如果是大写,要转成相应的小写字母。这个算法从两边扫描,到中间相遇,只需要一次线性扫描,复杂度是O(n),空间上是O(1)。代码如下:
public boolean isPalindrome(String s) { if(s==null || s.length()==0) return true; int l = 0; int r = s.length()-1; while(l<r) { if(!isValid(s.charAt(l))) { l++; continue; } if(!isValid(s.charAt(r))) { r--; continue; } if(!isSame(s.charAt(l),s.charAt(r))) { return false; } l++; r--; } return true; } private boolean isValid(char c) { if(c>='a' && c<='z' || c>='A' && c<='Z' || c>='0' && c<='9') return true; return false; } private boolean isSame(char c1, char c2) { if(c1>='A' && c1<='Z') c1 = (char)(c1-'A'+'a'); if(c2>='A' && c2<='Z') c2 = (char)(c2-'A'+'a'); return c1==c2; }回文串的判断和搜索是面试中经常遇到的基本问题,我在Facebook的面试中就遇到了这道题。在LeetCode中类似的题目还有Palindrome Number,Longest Palindromic Substring,Palindrome Partitioning等,Palindrome Number跟这道题比较类似,只是判断的是整数,而后面两道还是有一定难度的,有兴趣的朋友可以看看哈。