算法-字符串算法总结
2021-11-18 本文已影响0人
攻城老狮
思路：字符串类型的题目，一般都可以使用双指针的思路解决。双指针即可以将字符串看成一个由字符组成的数组，使用两个指针来定位一个子字符串。
1 反转字符串
思路：通过双指针分别指向子字符串的两端，对指定的子字符串进行翻转操作。
// 344. 反转字符串
// 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
}
// 541. 反转字符串 II
// 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for (int i = 0; i < ch.length; i += 2*k) {
int left = i;
int right = Math.min(ch.length - 1,i + k - 1);
while (left < right) {
char tmp = ch[left];
ch[left] = ch[right];
ch[right] = tmp;
left++;
right--;
}
}
return new String(ch);
}
}
// 151. 翻转字符串里的单词
// 给你一个字符串 s ，逐个翻转字符串中的所有单词 。单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。说明：输入字符串 s 可以在前面、后面或者单词间包含多余的空格。翻转后单词间应当仅用一个空格分隔。翻转后的字符串中不应包含额外的空格。
class Solution {
public String reverseWords(String s) {
StringBuilder sb = removeSpace(s);
reverseStr(sb,0,sb.length() - 1);
reverseWords(sb);
return sb.toString();
}
private StringBuilder removeSpace(String s) {
StringBuilder sb = new StringBuilder();
int left = 0;
int right = s.length() - 1;
while (left < right && s.charAt(left) == ' ') left++;
while (left < right && s.charAt(right) == ' ') right--;
while (left <= right) {
if (s.charAt(left) != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(s.charAt(left));
}
left++;
}
return sb;
}
private void reverseStr(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 reverseWord(StringBuilder sb) {
int start = 0;
int end = 0;
int n = sb.length();
while (end < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseStr(sb,start,end - 1);
start = end + 1;
end = start;
}
}
}
// 剑指 Offer 58 - II. 左旋转字符串
// 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder(s);
reverseString(sb,0,n - 1);
reverseString(sb,n,sb.length() - 1);
reverseString(sb,0,sb.length() - 1);
return sb.toString();
}
private void reverseString(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--;
}
}
}
2 双指针指向不同字符串
思路：定义两个指针指向不同的字符串，根据条件移动两个指针，使其满足题目规定的动作。
// 剑指 Offer 05. 替换空格
// 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
class Solution {
public String replaceSpace(String s) {
if (s == null || s.length() == 0) {
return s;
}
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == ' ') {
sb.append(" "); //添加2个位置，加上原本空格的1个位置刚好3个位置
}
}
if (sb.length() == 0) return s; //没有空格
int left = s.length() - 1;
s += sb.toString();
int right = s.length() - 1;
char[] ch = s.toCharArray();
while (left >= 0) {
if (ch[left] == ' ') {
ch[right--] = '0';
ch[right--] = '2';
ch[right--] = '%';
} else {
ch[right--] = ch[left];
}
left--;
}
return new String(ch);
}
}
3 滑动窗口（双指针结合哈希表）
思路：与统计字母出现次数相关的题目中，需要移动两个指针的同时，统计两个指针之间的字符串中字符出现的次数（类似滑动窗口）。其中，会经常需要使用哈希表来存储每个元素出现的次数。
// 剑指 Offer II 014. 字符串中的变位词
// 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。换句话说，第一个字符串的排列之一是第二个字符串的子串 。
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] arr = new int[26];
for (int i = 0; i < s1.length(); i++) {
arr[s1.charAt(i) - 'a']++;
arr[s2.charAt(i) - 'a']--;
}
if (allZero(arr)) return true;
for (int i = s1.length(); i < s2.length(); i++) {
arr[s2.charAt(i) - 'a']--;
arr[s2.charAt(i - s1.length()) - 'a']++;
if (allZero(arr)) return true;
}
return false;
}
private boolean allZero(int[] arr) {
for (int item : arr) {
if (item != 0) {
return false;
}
}
return true;
}
}
// 剑指 Offer II 015. 字符串中的所有变位词
// 给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。变位词 指字母相同，但排列不同的字符串。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s.length() < p.length()) return res;
int[] arr = new int[26];
for (int i = 0; i < p.length(); i++) {
arr[p.charAt(i) - 'a']++;
arr[s.charAt(i) - 'a']--;
}
if (allZero(arr)) res.add(0);
for (int i = p.length(); i < s.length(); i++) {
arr[s.charAt(i) - 'a']--;
arr[s.charAt(i - p.length()) - 'a']++;
if (allZero(arr)) res.add(i - p.length() + 1);
}
return res;
}
private boolean allZero(int[] arr) {
for (int item : arr) {
if (item != 0) {
return false;
}
}
return true;
}
}
// 剑指 Offer II 016. 不含重复字符的最长子字符串
// 给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, right = 0;
int[] arr = new int[256];
int maxLen = 0;
for (; right < s.length(); right++) {
arr[s.charAt(right)]++;
while (moreThan1(arr)) {
arr[s.charAt(left++)]--;
}
maxLen = Math.max(maxLen,right - left + 1);
}
return maxLen;
}
private boolean moreThan1(int[] arr) {
for (int item : arr) {
if (item > 1) {
return true;
}
}
return false;
}
}
// 剑指 Offer II 017. 含有所有字符的最短字符串
// 给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。如果 s 中存在多个符合条件的子字符串，返回任意一个。
class Solution {
public String minWindow(String s, String t) {
Map<Character,Integer> map = new HashMap<>();
for (char c : t.toCharArray()) {
map.put(c,map.getOrDefault(c,0) + 1);
}
int count = map.size();
int left = 0, right = 0, minLeft = 0, minRight = 0;
int minLen = Integer.MAX_VALUE;
while (right < s.length() || (right == s.length() && count == 0)) {
if (count > 0) {
char rightCh = s.charAt(right);
if (map.containsKey(rightCh)) {
map.put(rightCh,map.get(rightCh) - 1);
if (map.get(rightCh) == 0) {
count--;
}
}
right++;
} else {
if (right - left < minLen) {
minLen = right - left;
minLeft = left;
minRight = right;
}
char leftCh = s.charAt(left);
if (map.containsKey(leftCh)) {
map.put(leftCh,map.get(leftCh) + 1);
if (map.get(leftCh) == 1) {
count++;
}
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft,minRight);
}
}
4 回文字符串
思路：回文是一类特殊的字符串。不管是从头到尾还是颠倒过来从尾到头，得到的内容是一样的。
// 剑指 Offer II 018. 有效的回文
// 给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。本题中，将空字符串定义为有效的 回文串 。
class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
char leftCh = s.charAt(left);
char rightCh = s.charAt(right);
if (!Character.isLetterOrDigit(leftCh)) {
left++;
} else if (!Character.isLetterOrDigit(rightCh)) {
right--;
} else {
leftCh = Character.toLowerCase(leftCh);
rightCh = Character.toLowerCase(rightCh);
if (leftCh != rightCh) return false;
left++;
right--;
}
}
return true;
}
}
// 剑指 Offer II 019. 最多删除一个字符得到回文
// 给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
class Solution {
public boolean validPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) break;
left++;
right--;
}
return left == right || isPalindrome(s,left + 1,right) || isPalindrome(s,left,right - 1);
}
private boolean isPalindrome(String s,int left,int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
}
// 剑指 Offer II 020. 回文子字符串的个数
// 给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
class Solution {
public int countSubstrings(String s) {
if (s == null || s.length() == 0) return 0;
int count = 0;
for (int i = 0; i < s.length(); i++) {
count += countPalindrome(s,i,i);
count += countPalindrome(s,i,i + 1);
}
return count;
}
private int countPalindrome(String s,int left,int right) {
int count = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
count++;
left--;
right++;
}
return count;
}
}
