一、前言
字符串是我们编程最常使用的数据类型，在算法领域字符串的题目也非常多，本文通过分析字符串最经典的操作进行总结记录，对于我们沉淀字符串类的算法是有帮助的，算法虽难学，但是我相信多实操，多总结，总有一天可以提高我们的算法思维。
二、字符串经典用法
1、间接借助双指针法遍历字符串
我们对于字符串操作时，可以将字符串转换为字符数组，在数组中，我们有通过双指针法来完成多种形式遍历，这样在字符串中也完美借助了双指针法的能力。之前有总结双指针在数组中的经典应用，有兴趣的朋友可以收藏下。
通过双指针，我们能够轻松解决字符串整体反转,字符串部分反转等经典题目。
三、实战
leetcode344. 反转字符串
class Solution {
public void reverseString(char[] s) {
int start = 0;
int end = s.length-1;
while(start<end) {
char a = s[start];
char b = s[end];
s[start] = b;
s[end] = a;
start++;
end--;
}
}
}
上面通过双指针法实现字符串整体反转。
class Solution {
public String reverseStr(String s, int k) {
//0 2 0 1 2 3 4 5 6
char[] chars = s.toCharArray();
for(int i=0; i<s.length(); i = i + 2*k) {
//下标从0开始，因此需要处理的结尾下标需要-1
int temp = i + k -1;
int end = 0;
//不可以越界
if(temp <= s.length()-1) {
end = temp;
} else {
//不可以越界
end = s.length() -1;
}
System.out.println(i+"="+end);
reverseChars(chars, i, end);
}
return new String(chars);
}
public void reverseChars(char[] chars, int start, int end) {
while(start < end) {
char a = chars[start];
char b = chars[end];
chars[start] = b;
chars[end] = a;
start++;
end--;
}
}
}
通过双指针法完成字符串部分反转
leetcode151. 反转字符串中的单词
class Solution {
public String reverseWords(String s) {
//移除空格
StringBuilder ss = removeSpace(s);
//使用双指针法实现原地反转
//先整体反转一次 再单独反转每个单词
char[] chars = ss.toString().toCharArray();
//整体反转
int start = 0;
int end = chars.length - 1;
while(start < end) {
char a = chars[start];
char b = chars[end];
chars[start] = b;
chars[end] = a;
start++;
end--;
}
//再每个单词单独反转
for(int i=0; i<chars.length; ) {
int e = i;// "the sky is blue"
//遇到了空串，或者结尾了，就需要反转
while(chars.length-1 == e ||( e < chars.length && chars[e] != ' ') ) {
e++;
}
reverseChars(chars,i, e-1);
System.out.println(i+"="+e);
i=e+1;
}
//"the sky is blue"
return new String(chars);
}
public void reverseChars(char[] chars, int start, int end) {
while(start < end) {
char a = chars[start];
char b = chars[end];
chars[start] = b;
chars[end] = a;
start++;
end--;
}
}
private StringBuilder removeSpace(String s) {
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') start++;
while (s.charAt(end) == ' ') end--;
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
return sb;
}
}
通过双指针完成字符串整体反转和部分反转。
四、总结
双指针在数组中的用法，使用到了字符串上面，实现字符串原地处理字符数据的能力。
