字符串

认识字符串

在学习算法的过程中，我们经常会遇到输入是字符串的题目，然后利用各种技巧例如标准库、动态规划，或者是一些字符串遍历的技巧来解决问题。

反转字符串

力扣题目链接
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

• 双指针技巧，每次交换最左与最右的字符

class Solution {
    public void reverseString(char[] s) {
        for (int i = 0; i < s.length / 2; i++) {
            char tem = s[s.length - i - 1];
            s[s.length - i - 1] = s[i];
            s[i] = tem;
        }
    }
}

反转字符串Ⅱ

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

• 直接模拟，每隔 2k 个字符，反转前 k 个字符，若不够 2k 个字符，要么全部反转（长度小于 k），要么反转前 k 个（长度大于 k）

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }
    public void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

翻转字符串里的单词

力扣题目链接
给你一个字符串 s，请你反转字符串中单词的顺序。

• 双指针，一个指针指向单词末尾，另一个指针通过移动，发掘所有单词字母，以及跳过所有空格
• 调用 substring() API 完成取出单词的任务

class Solution {
    public String reverseWords(String s) {
        s = s.trim();// 去除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while (i >= 0) {
            // 搜索首个空格
            while (i >= 0 && s.charAt(i) != ' ') {
                i--;
            }
            res.append(s.substring(i + 1, j + 1) + ' ');
            // 跳过单词间的空格
            while (i >= 0 && s.charAt(i) == ' ') {
                i--;
            }
            j = i;
        }
        // 增加trim是为了去掉每次添加单词时固定加上的空格
        return res.toString().trim();
    }
}

找出字符串中第一个匹配项的下标

力扣题目链接
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。

• 有时候没必要给自己增加太多负担，这个世界本身就是一个巨大的草台班子
• 偶尔调调库也是挺放松的一件事情

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

重复的子字符串

力扣题目链接
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

• 一个好玩的结论就是，让str = s + s，直接判断 str 中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);
    }
}

Z字形变换

力扣题目链接
将一个给定字符串 s 根据给定的行数 numRows，以从上往下、从左到右进行 Z 字形排列。

• 若行数为 4，则 s 中每一个字符对应的行号为 1234321234321……
• 所以新建一个标志数组，用于标识每个字符的行号

class Solution {
    public String convert(String s, int numRows) {
        // 如果行数为 1，直接返回原字符串
        if (numRows == 1) {
            return s;
        }
        // 用于存储每个字符所在的行号
        int[] flag = new int[s.length()];
        boolean fla = true;
        // i 表示当前字符所在的行号，初始为 1
        int i = 1;
        for (int j = 0; j < flag.length; j++) {
            // 记录当前字符所在的行号
            flag[j] = i;
            if (i == numRows) {
                // 当到达最后一行时，开始递减
                fla = false;
            } else if (i == 1) {
                // 当到达第一行时，开始递增
                fla = true;
            }
            if (fla) {
                // 递增行号
                i++;
            } else {
                // 递减行号
                i--;
            }
        }
        StringBuilder res = new StringBuilder();
        // 按行号遍历
        for (int m = 1; m <= numRows; m++) {
            for (int j = 0; j < flag.length; j++) {
                if (flag[j] == m) {
                    // 按行号依次添加字符到结果中
                    res.append(s.charAt(j));
                }
            }
        }
        return res.toString();
    }
}

正则表达式匹配

力扣题目链接
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 . 和 * 的正则表达式匹配。其中，. 匹配任意单个字符，* 匹配零个或多个前面的那一个元素。所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

整数转罗马数字

力扣题目链接
给定一个数字，将其转换为罗马数字，转换规则不再赘述。

• 使用哈希表与贪心思路解决问题
• TreeSet 是有序的，HashSet 本身是无序的

class Solution {
    public String intToRoman(int num) {
        TreeMap<Integer, String> map = new TreeMap<>(Collections.reverseOrder());
        map.put(1000, "M");
        map.put(900, "CM");
        map.put(500, "D");
        map.put(400, "CD");
        map.put(100, "C");
        map.put(90, "XC");
        map.put(50, "L");
        map.put(40, "XL");
        map.put(10, "X");
        map.put(9, "IX");
        map.put(5, "V");
        map.put(4, "IV");
        map.put(1, "I");
        StringBuilder result = new StringBuilder();
        for (int value : map.keySet()) {
            while (num >= value) {
                result.append(map.get(value));
                num -= value;
            }
        }
        return result.toString();
    }
}

字母异位词分组

力扣题目链接
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。

• 将排序后的字符串作为键，排序前的字符串 List 作为值，逐个添入

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

无重复字符的最长子串

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

• 滑动窗口模板

//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
	//当前考虑的元素（一般是 right 指向的那个元素）
	while (l <= r && check()) {//区间[left,right]不符合题意
        //扩展左边界
    }
    //区间[left,right]符合题意，统计相关信息
}

• 利用 set 来判断是否包含重复字符，若窗口内有重复字符串，则 left 指针一直向后移动直到窗口内无重复字符串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        HashSet<Character> set = new HashSet<>();
        char[] str = s.toCharArray();
        for (int left = 0, right = 0; right < s.length(); right++) {
            char ch = str[right];
            while (set.contains(ch)) {
                set.remove(str[left]);
                left++;
            }
            set.add(ch);
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

找到字符串中所有字母异位词

力扣题目链接
给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

• 定长滑动窗口，维护窗口内各字母的出现次数然后进行比对即可，比对结束后 left 往右移动 1 个位置（即 left 对应的字母出现次数减一）
• left 恒等于 right - length + 1

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int[] cntP = new int[26];
        int[] cntS = new int[26];
        for (char c : p.toCharArray()) {
            cntP[c - 'a']++;// 统计p的字母及次数
        }
        for (int right = 0; right < s.length(); right++) {
            cntS[s.charAt(right) - 'a']++;
            int left = right - p.length() + 1;
            if (left < 0) {
                continue;
            }
            if (Arrays.equals(cntS, cntP)) {
                ans.add(left);
            }
            cntS[s.charAt(left) - 'a']--;
        }
        return ans;
    }
}

最小覆盖子串

力扣题目链接
给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “”。

• 滑动窗口，枚举右侧边界，直到包含 t 中所有字符
• 随后移动左侧边界，寻找是否有更短的情形
• 判断是否包含，使用的是哈希数组
• A ~ Z 是 65 ~ 90
• a ~ z 是 97 ~ 122
• int[a] 也就是int[97]

class Solution {
    public String minWindow(String S, String t) {
        char[] s = S.toCharArray();
        int m = s.length;
        int ansLeft = -1;
        int ansRight = m;
        int[] cntS = new int[128];
        int[] cntT = new int[128];
        for (char c : t.toCharArray()) {
            cntT[c]++;
        }
        int left = 0;
        for (int right = 0; right < s.length; right++) {
            cntS[s[right]]++;
            while (isCovered(cntS, cntT)) {
                if (right - left < ansRight - ansLeft) {
                    ansLeft = left;
                    ansRight = right;
                }
                cntS[s[left]]--;
                left++;
            }
        }
        return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
    }
    private boolean isCovered(int[] cntS, int[] cntT) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        return true;
    }
}

最长回文子串

力扣题目链接
给你一个字符串 s，找到 s 中最长的回文子串。

• 中心扩散法
• 首先往左寻找与当期位置相同的字符，直到遇到不相等为止
• 然后往右寻找与当期位置相同的字符，直到遇到不相等为止
• 最后左右双向扩散，直到左和右不相等

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int len = 1;
        int ans = 0;
        int maxLeft = 0;
        for (int i = 0; i < s.length(); i++) {
            int left = i - 1;
            int right = i + 1;
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                left--;
                len++;
            }
            while (right < s.length() && s.charAt(right) == s.charAt(i)) {
                right++;
                len++;
            }
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                len = len + 2;
                left--;
                right++;
            }
            if (len > ans) {
                ans = len;
                maxLeft = left;
            }
            len = 1;
        }
        return s.substring(maxLeft + 1, maxLeft + ans + 1);
    }
}

划分字母区间

力扣题目链接
给你一个字符串 s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s。返回一个表示每个字符串片段的长度的列表。

• 记录每个字母最后出现的下标位置
• 开始遍历，维护当前字符子串能够达到的最大位置
• 当遍历到的位置与最大位置相等时，即为符合条件的划分结果

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        int length = s.length();
        for (int i = 0; i < length; i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> list = new ArrayList<>();
        int start = 0, right = 0;
        for (int i = 0; i < length; i++) {
            right = Math.max(right, last[s.charAt(i) - 'a']);
            if (i == right) {
                list.add(right - start + 1);
                start = right + 1;
            }
        }
        return list;
    }
}