1. 基本串操作
1.1 验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
思路
首先将所给字符串转换为只含有字母数字字符的字符串，然后通过双指针进行比较。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public boolean isPalindrome(String s) {
StringBuilder cnt=new StringBuilder();
int n=s.length();
for(int i=0;i<n;i++){
char p=s.charAt(i);
if(Character.isDigit(p)){
cnt.append(p);
}else if(Character.isLetter(p)){
cnt.append(Character.toLowerCase(p));
}
}
int left=0,right=cnt.length()-1;
while(left<right){
if(cnt.charAt(left)!=cnt.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
|
1.2 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
思路
横向扫描，依次字符串遍历数组，每次更新当前的最长公共前缀。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public String longestCommonPrefix(String[] strs) {
int n=strs.length;
String ans=strs[0];
for(int i=1;i<n;i++){
ans=find(strs[i],ans);
}
return ans;
}
public String find(String str1,String str2){
int len=Math.min(str1.length(),str2.length());
int id=0;
while(id<len&&str1.charAt(id)==str2.charAt(id)){
id++;
}
return str1.substring(0,id);
}
}
|
1.3 压缩字符串
给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
- 如果这一组长度为
1 ，则将字符追加到 s 中。
- 否则，需要向
s 追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
思路
双指针，一个指针指向当前数组，一个指针指向压缩后的数组，依次判断。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int compress(char[] chars) {
int n=chars.length;
if(n==1) return 1;
int index=0;
for(int i=0;i<n;i++){
if(i<n-1&&chars[i]==chars[i+1]){
int pre=i;
while(i<n-1&&chars[i]==chars[i+1]){
i++;
}
int num=i-pre+1;
String tot=String.valueOf(num);
chars[index++]=chars[pre];
for(int j=0;j<tot.length();j++){
chars[index++]=tot.charAt(j);
}
}else{
chars[index++]=chars[i];
}
}
return index;
}
}
|
2. 串模式匹配
2.1 找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
思路
直观思路：暴力枚举，每次让needle与haystack进行匹配，直到找到匹配项。
进阶：KMP算法。(算法难度较高，证明较难)
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public int strStr(String haystack, String needle) {
int n=haystack.length(),m=needle.length();
int[] pre=new int[m];
for(int i=1,j=0;i<m;i++){
while(j>0&&needle.charAt(i)!=needle.charAt(j)){
j=pre[j-1];
}
if(needle.charAt(i)==needle.charAt(j)){
j++;
}
pre[i]=j;
}
for(int i=0,j=0;i<n;i++){
while(j>0&&needle.charAt(j)!=haystack.charAt(i)){
j=pre[j-1];
}
if(needle.charAt(j)==haystack.charAt(i)){
j++;
}
if(j==m){
return i-m+1;
}
}
return -1;
}
}
|
2.2 重复的子字符串
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
思路
KMP算法寻找最小重复子串，然后判断该字符串是否由该最小重复子串组成。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean repeatedSubstringPattern(String s) {
int n=s.length();
int[] pi=new int[n];
for(int i=1,j=0;i<n;i++){
while(j>0&&s.charAt(i)!=s.charAt(j)){
j=pi[j-1];
}
if(s.charAt(j)==s.charAt(i)){
j++;
}
pi[i]=j;
}
return pi[n-1]!=0&&n%(n-pi[n-1])==0;
}
}
|
2.3 数组中的字符串匹配
给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 words[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。
思路
暴力枚举，二重循环依次判断。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<String> stringMatching(String[] words) {
List<String> cnt=new ArrayList<>();
int n=words.length;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i!=j&&words[j].contains(words[i])){
cnt.add(words[i]);
break;
}
}
}
return cnt;
}
}
|