力扣刷题篇之【字符串篇】（一）_无满*的博客-爱代码爱编程
✨hello，愿意点进来的小伙伴们，你们好呐！
✨ 🐻🐻系列专栏：【力扣刷题篇】
🐲🐲本篇内容：字符串刷题篇
🐯🐯作者简介:一名现大二的三非编程小白
1.最长公共前缀
链接: 最长公共前缀
对于该题，有以下两种解法：
1.纵向判断：
我们可以遍历数组中的字符串，对字符串的每一个字符都进行一一比对，判断最长公共前缀。
那要怎么实现对字符串中字符的一一判断呢？
我们可以定义一个整型变量来存放数组中第一个字符串的长度，并使用for循环遍历该字符串，将该字符串的每一个字符取出来，又进行for循环遍历其余的字符串，判断是否字符不同或者已经遍历到最短字符串的最后一个字符，返回第一个字符串的截取字符，若遍历完没有返回，则返回第一个字符串。
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0){
return "";
}
int length = strs[0].length();
int count = strs.length;
for(int i = 0;i < length;i++){
char ch = strs[0].charAt(i);
for(int j = 1;j < count;j++){
if(i == strs[j].length() || ch != strs[j].charAt(i)){
return strs[0].substring(0,i);
}
}
}
return strs[0];
}
}
解法2：横向判断
我们可以用横向判断，对比找到两个字符串之间最长公共前缀，将该判断写成一个方法。用for循环来调用该方法对字符串寻找公共前缀
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0){
return "";
}
String tmp = strs[0];
for(int i = 1;i < strs.length ;i++){
tmp = longestCommonPrefix(tmp,strs[i]);
}
return tmp;
}
public String longestCommonPrefix(String str1, String str2){
int length = Math.min(str1.length(),str2.length());
int index = 0;
while(index < length && str1.charAt(index) == str2.charAt(index)){
index++;
}
return str1.substring(0,index);
}
}
2. 反转字符串中的单词
链接: 反转字符串中的单词
刚看到这道题的时候我想了一个很low的办法，我们可以先将字符串的前后空格和字符串中多余的空格去掉，再将字符串整体反转，最后将一个个单词反转。虽然Java中有该类库，但是我还是自己实现了这些方法。
class Solution {
public String reverseWords(String s) {
StringBuilder sb = trimSpaces(s);
reverse(sb,0,sb.length() - 1);
reverseEachWord(sb);
return sb.toString();
}
public StringBuilder trimSpaces(String s){//去除前后空格
StringBuilder stringBuilder = new StringBuilder();
int i = 0;
while(s.charAt(i) == ' '){
//前面空格
i++;
}
int j = s.length() - 1;
while(s.charAt(j) == ' '){
j--;
}
while(i <= j){
char ch = s.charAt(i);
if(ch != ' '){
stringBuilder.append(ch);
}else if(stringBuilder.charAt(stringBuilder.length() - 1) != ' '){
stringBuilder.append(ch);
}
i++;
}
return stringBuilder;
}
public void reverse(StringBuilder sb, int left, int right){//字符串翻转
while(left < right){
char tmp = sb.charAt(left);
sb.setCharAt(left,sb.charAt(right));
sb.setCharAt(right,tmp);
left++;
right--;
}
}
public void reverseEachWord(StringBuilder sb){//翻转字符串单词
int length = sb.length();
int state = 0;
int end = 0;
while(state < length){
while(end < length && sb.charAt(end) != ' '){
end++;
}
reverse(sb,state,end - 1);
end++;
state = end;
}
}
}
但是我们会发现这种思路的空间复杂度和时间复杂度都较高，而且运用Java的类库就可以实现，有没有更巧妙的方法呢？当然是有的啦。
思路：
1. 我们也要先将字符串前后空格去除，然后定义双指针，指向最左和最右，再定义index先等于右指针。
2. 我们要通过遍历让index指向right的前一个空格，找到最后的一个单词。 
3. 然后for循环中将该单词存储到StringBuffer变量中。
4. 然后判断要存储的是否为该字符串的第一个单词，若不是则存入一个空格。
5. 最后让right = index ，重新进行遍历查找。
class Solution {
public String reverseWords(String s) {
int left = 0, right = s.length() - 1;
// 去掉字符串开头的空白字符
while (left <= right && s.charAt(left) == ' ') {
++left;
}
// 去掉字符串末尾的空白字符
while (left <= right && s.charAt(right) == ' ') {
--right;
}
StringBuffer sb = new StringBuffer();
int index = right;
while(left <= right){
while(index >= left && s.charAt(index) != ' '){//找到范围
index--;
}
for(int i = index + 1;i <= right;i++){
sb.append(s.charAt(i));
}
if(index > left){
sb.append(' ');
}
while(index >= left && s.charAt(index) == ' '){
index--;
}
right = index;
}
return sb.toString();
}
}