相关概念

1. 字符串：由零个或多个字符组成的有限序列。

2. 子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。
   真子串是不包含自身的所有子串。

3. 主串：包含子串的串相应的称为主串

4. 字符位置：字符在序列中的序号为该字符在串中的位置

5. 子串位置：子串第一个字符在主串中的位置

6. 空格串：由一个或多个空格组成的串（与空串不同）

7. 串相等：当且仅当两个串的长度相等并对应位置上的字符都相等时，这两个串才是相等的。
   所有空串是相等的。

字符串的基本概念与简单实现（c语言描述）

KMP算法（困难）

回文串

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

回文串：一串正着读和反着读都是一样的一种特殊字符串

俩个方法：

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

函数反转

对于每个语言函数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--;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

俩边向中心靠拢

比如对一个字符串 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

刷题巩固

键盘行
验证回文