文章目录

• 前言
• 题目&推荐
• • 1.经验+技巧
  • 2.题目列表
• 开撸
• • 1.lc344 反转字符串
  • 2.lc541 反转字符串 II
  • 3.剑指Offer 05替换空格
  • 4.lc443 压缩字符串
  • 5.lc14 最长公共前缀
  • 6.剑指Offer58-II.左旋转字符串

前言

对于字符串的相关题目，主要分为两类

• 字符串操作
• 字符串匹配

本文主要介绍字符串操作相关，包括反转，压缩，替换 等

字符串基本理论知识可参考：java字符串（String & StringBuilder）
字符串匹配可参考：leetcode字符串小结（下）

题目&推荐

1.经验+技巧

（1）熟悉字符串的操作
字符串的操作，有一定技巧性，并且还需要熟悉相关API的使用

比如String常用的有： 截取操作substring(int beginIndex, int endIndex)；字符串转换为字符数组char[ ] toCharArray()；替换 replace(char searchChar, char newChar)等

StringBuilder中：反转操作 reverse()；字符串连接 append()；转换为String toString()等

（2）双指针
与数组一样，双指针在字符串中同样作用很大（数组和字符串很多相似之处）

关于双指针的详细介绍，可以参见： 双指针。在很多想要暴力的场景下，不妨想想双指针!尤其是快慢指针和前后指针！

2.题目列表

开撸

1.lc344 反转字符串

力扣链接 lc344

题目描述：

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

示例：

输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]

如果题目没有要求原地修改，就是一般的反转，那就很简单：

public static String reverseString(char[] s){char[] newS = new char[s.length];for(int i=0;inewS[i] = s.[s.length-i-1];}return newS;
}

言归正传，如果是原地修改的话，那可以使用双指针

public void reverseString(char[] s) {/*定义两个指针，一个指向前面，一个指向后面两个指针同时向中间移动，并交换元素。*/int p = 0;int q = s.length-1;while(pchar tmp = s[p];s[p] = s[q];s[q] = tmp;p++;q--;}}

时间复杂度：O(N)，其中 N 为字符数组的长度。一共执行了 N/2 次的交换。
空间复杂度：O(1)。只使用了常数空间来存放若干变量

2.lc541 反转字符串 II

力扣题目链接 lc541

题目描述：

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例：

输入：s = “abcdefg”, k = 2 输出：“bacdfeg”
输入：s = “abcd”, k = 2 输出：“bacd”

3.剑指Offer 05替换空格

题目链接 offer05

描述：

请实现一个函数，把字符串 s 中的每个空格替换成"%20"

示例

输入：s = “We are happy.”
输出：“We%20are%20happy.”

Solution：
善于运用StringBuilder

 public String replaceSpace(String s) {StringBuilder sb = new StringBuilder();for(int i=0;iif(s.charAt(i)==' ')sb.append("%20");elsesb.append(s.charAt(i));}return sb.toString();}

4.lc443 压缩字符串

题目链接：lc443

题目描述

给你一个字符数组 chars ，请使用下述算法压缩

示例：

输入：chars = [“a”,“a”,“b”,“b”,“c”,“c”,“c”]
输出：返回 6 ，输入数组的前 6 个字符应该是：[“a”,“2”,“b”,“2”,“c”,“3”]

solution

public int compress(char[] chars) {// 定义快慢指针，和需要插入的索引indexint slow=0,fast,index=0;while(slowfast = slow;// 1.如果快指针指向的元素与慢指针相同，快指针一直移动while(fast1){String cntStr = Integer.toString(cnt);for(int i=0;i

5.lc14 最长公共前缀

题目链接：lc14

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串

示例：

输入：strs = [“flower”,“flow”,“flight”] ； 输出：“fl”

solution ：

public String longestCommonPrefix(String[] strs) {// 横向扫描，挨个比较// 先假设最长前缀就是第一个字符串String ans = strs[0];//将第一个分别与后面的字符串进行前缀比较for(int i=1;iint j=0;while(j

6.剑指Offer58-II.左旋转字符串

题目链接：offer58 左旋转字符串

题目描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例：

输入: s = “abcdefg”, k = 2
输出: “cdefgab”

solution 1：

class Solution {public String reverseLeftWords(String s, int n) { char[] chs = s.toCharArray();for(int j=0;jchar tmp = chs[0];for (int i = 0; i < s.length() - 1; i++)chs[i] = chs[i + 1];chs[s.length() - 1] = tmp;}String t = new String(chs);return t;}
}

solution 2——切片法：

（比较直观的解法）

 public static String reverseLeftWords(String s, int n) {String src = s;// 循环表示 n 次移位for(int i=0;i// 获取首字母char first = src.charAt(0);// 通过subString截取后部分String last = src.substring(1);// 将 last和 first 拼接src = last + first;}return src;}

结果：
执行用时太长，pass

（看破本质一步到位法）
思路：

代码：

public String reverseLeftWords(String s, int n) {return s.substring(n)+s.substring(0,n);}

结果：时间复杂度大大提升了

Solution3：