有效回文字符串(Valid palindrome)

题目描述 

 

思路分析

代码实践 

java:

public class Solutation1 {//定义一个方法，判断是否是有效数字或者字母private static boolean isValid(char c) {//如果不是字母或者数字，那就返回一个flase//这里调用了Character类里面的方法return Character.isLetter(c) || Character.isDigit(c);}//判断两个字母是否相等，这里还要忽略大小写private static boolean isEqual(char a,char b) {return Character.toLowerCase(a) == Character.toLowerCase(b);}//主函数public static boolean isPalindrome(String s) {if (s == null) {return false;}int left = 0, right = s.length() - 1;while (left < right) {//非数字左边是++循环while (left < right && !isValid(s.charAt(left))) {left++;} while (left < right && !isValid(s.charAt(right))) {right--;}//上面都跳到正确的位置//开始比较if (left < right && !isEqual(s.charAt(left), s.charAt(right))) {return false;//只要有一个对比不等就不是回文}left++;right--;}//上面如果没有跳到return,直接返回truereturn true;}public static void main(String[] args) {boolean res = isPalindrome("1b , 1");if (res == true) {System.out.println("它是回文串");}}
}

 运行结果：

下面分析一下它的时间复杂度

 

所以时间复杂度是O(n)

下面用c++代码解决：

#include <iostream>
#include <cctype> // 用于字符处理函数using namespace std;bool isValid(char c) {// 如果不是字母或者数字，返回falsereturn isalnum(c);
}bool isEqual(char a, char b) {// 忽略大小写比较两个字符是否相等return tolower(a) == tolower(b);
}bool isPalindrome(string s) {if (s.empty()) {return true; // 空字符串被认为是回文串}int left = 0, right = s.length() - 1;while (left < right) {// 非字母或数字的字符，左指针右移while (left < right && !isValid(s[left])) {left++;}// 非字母或数字的字符，右指针左移while (left < right && !isValid(s[right])) {right--;}// 开始比较字符if (left < right && !isEqual(s[left], s[right])) {return false; // 只要有一个对比不等就不是回文}left++;right--;}return true;
}int main() {bool res = isPalindrome("1b , 1");if (res == true) {printf("it is palindrome\n");} else {printf("it is not palindrome");}return 0;
}

运行结果：

 

上面说几个点：

1.这里引入了c语言当中的一个头文件，去进行字符判断的操作

2.下面这里为什么不进行NULL的判断

正确的方法来检查字符串是否为空。如果你尝试将空指针传递给这个函数，编译器会报错，因为它不接受指针作为参数。所以不需要额外检查指针是否为 NULL 

上面的时间算法复杂度还是O(n)

好了祝早安午安晚安