首页 > 代码库 > [leetcode]Valid Palindrome
[leetcode]Valid Palindrome
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.
算法思路：
思路1：首尾两指针，在原来的字符串的基础上，进行扫描判断。空间复杂度O(1)，时间O(n)，一次扫描。
1 public class Solution { 2 public boolean isPalindrome(String s) { 3 s = s.trim().toLowerCase(); 4 int i = 0; 5 int j = s.length() - 1; 6 while(i < s.length() && !isValid(s.charAt(i))) i++; 7 while(j >= 0 && !isValid(s.charAt(j))) j--; 8 while(i <= j){ 9 char a = s.charAt(i);10 char b = s.charAt(j);11 if(a != b){12 return false;13 }else{14 i++;15 while(i < s.length() && !isValid(s.charAt(i))) i++;16 j--;17 while(j >= 0 && !isValid(s.charAt(j))) j--;18 }19 }20 return true;21 }22 private boolean isValid(char c){23 if((c >= ‘a‘ && c <= ‘z‘) || (c >= ‘A‘ && c <= ‘Z‘) || (c >= ‘0‘ && c <= ‘9‘) ) return true;24 return false;25 }26 }
思路2：第一遍扫描，将合法字符保留在另一个字符串s中，第二遍扫描s。空间复杂度O(1)，时间复杂度O(n)，两次扫描。
比较简单，不实现了
[leetcode]Valid Palindrome
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。