七日算法先导（七）——字符串

作者：秋名山码民

2022 年 8 月 09 日
陕西
本文字数：1044 字
阅读完需：约 3 分钟

回文串

字符串的基本概念上面俩篇文章都讲的很清楚了，其中还有一个回文串，我们现在来看一下：

<font color = red>回文串：一串正着读和反着读都是一样的一种特殊字符串

俩个方法：

直接函数反转
中心拓展方法

函数反转

对于每个语言函数 api 可能不同，我们统称为 reverse 函数

我们输入的字符串类型定位 string 型，然后使用 reverse 函数就可以,然后我们直接比较 str1 与 str2 是否相等，相等的话那么就表示输入的字符串为回文串。

reverse(str2.begin(), str2.end());

假设，题目中禁止了反转函数那么我们可以手写一个函数，也是比较容易实现的：

void reverse(char * str){    int len=strlen(str);    char *ch=str+len-1;    while(len>1)    {        char tmp=*str;        *str=*ch;        *ch='\0';               reverse(str+1);         *ch = tmp;        len--;    }}

复制代码

俩边向中心靠拢

比如对一个字符串 ababa，选择 left = 0，和 right = n-1，如果俩个相等，则 left++，right--当 left 与 right 俩个所指的数不等，则不是回文，直接退出，反之，left == right 时候，就是回文串

class Solution {    public boolean isPalindrome(String s) {        int n = s.length();        int left = 0, right = n - 1;        //        while (left < right) {            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {                ++left;            }            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {                --right;            }            if (left < right) {                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {                    return false;                }                ++left;                --right;            }        }        return true;    }}