字符串经典基础面试题

关卡名	字符串经典基础面试题	我会了✔️
内容	1.理解字符串反转的处理方法	✔️
	2.熟练掌握回文串的判断方法	✔️
	3.掌握字符串中搜索第一个唯一字符的方法	✔️
	4.掌握判断是否互为字符串重排的处理技巧	✔️

1 反转的问题

我们知道反转是链表的一个重要考点，反转同样是字符串的重要问题。常见问题也就是在LeetCode中列举的相关题目：
【1】LeetCode344. 反转字符串：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。【2】LeetCode541. K个一组反转：给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
【3】LeetCode.917. 仅仅反转字母：·给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。
【4】LeetCode151. 反转字符串里的单词：给你一个字符串 s ，逐个反转字符串中的所有单词。【5】LeetCode.557. 反转字符串中的单词 III：给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
这几个题目你是否发现前三道就是要么反转字符，要么反转里面的单词。针对字符的反转又可以变换条件造出多问题。我们就从基本问题出发，各个击破。

1.1 反转字符串

LeetCode344. 题目要求：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例1：

输入：s = ["h","e","l","l","o"]

输出：["o","l","l","e","h"]

示例2：

输入：s = ["H","a","n","n","a","h"]

输出：["h","a","n","n","a","H"]

这是最基本的反转题，也是最简单的问题，使用双指针方法最直接。具体做法是:
对于长度为 N 的待被反转的字符数组，我们可以观察反转前后下标的变化，假设反转前字符数组为 s[0] s[1] s[2] ... s[N - 1]，那么反转后字符数组为 s[N - 1] s[N - 2] ... s[0]。比较反转前后下标变化很容易得出 s[i] 的字符与 s[N - 1 - i] 的字符发生了交换的规律，因此我们可以得出如下双指针的解法：

将 left 指向字符数组首元素，right 指向字符数组尾元素。
当 left < right：

        ○交换 s[left] 和 s[right]；
        ○left 指针右移一位，即 left = left + 1；
        ○right 指针左移一位，即 right = right - 1。

当 left >= right，反转结束，返回字符数组即可。

public void reverseString(char[] s) {
       if (s == null || s.length() == 0) {
            return ;
        }
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
}

1.2 K个一组反转

LeetCode541 这个题，我感觉有点没事找事，先看一下要求：
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

输入：s = "abcdefg", k = 2

输出："bacdfeg"

示例2：

输入：s = "abcd", k = 2

输出："bacd"

我们直接按题意进行模拟就可以：反转每个下标从 2k的倍数开始的，长度为 k的子串。若该子串长度不足 k，则反转整个子串。

public String reverseStr(String s, int k) {
       if (s == null || s.length() == 0) {
            return s;
        }
        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--;
        }
    }

1.3 仅仅反转字母

LeetCode.917 这个题有点难度，我们来看一下：
给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。

示例1：
输入："ab-cd"
输出："dc-ba"

示例2：
输入："a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"

示例3：
输入："Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"

这里第一眼感觉不是特别复杂，同样从两头向中间即可，但问题是"-"不是均匀的有些划分的段长，有的短，这就增加了处理的难度。

方法1：使用栈

将 s 中的所有字母单独存入栈中，所以出栈等价于对字母反序操作。（或者，可以用数组存储字母并反序数组。）
然后，遍历 s 的所有字符，如果是字母我们就选择栈顶元素输出。

class Solution {
    public String reverseOnlyLetters(String S) {
    
        Stack<Character> letters = new Stack();
        for (char c: S.toCharArray())
            if (Character.isLetter(c))
                letters.push(c);

        StringBuilder ans = new StringBuilder();
        for (char c: S.toCharArray()) {
            if (Character.isLetter(c))
                ans.append(letters.pop());
            else
                ans.append(c);
        }

        return ans.toString();
    }
}

方法2：拓展双转指针

一个接一个输出 s 的所有字符。当遇到一个字母时，我们希望找到逆序遍历字符串的下一个字母。
所以我们这么做：维护一个指针 j 从后往前遍历字符串，当需要字母时就使用它。

class Solution {
    public String reverseOnlyLetters(String S) {
       if (S == null || S.length() == 0) {
            return S;
        }
        StringBuilder ans = new StringBuilder();
        int j = S.length() - 1;
        for(int i=0;i<S.length();i++){
            if(Character.lsLetter(S.charAt(i)){
                while(!Character.isLetter(S.charAt(j))){
                    j--;
                }
                ans.append(S.charAt(j--));
            } else {
                ans.append(S.charAt(i));
            }
        }
        return ans.toString();
    }
}

1.4 .反转字符串里的单词

LeetCode151 给你一个字符串 s ，逐个反转字符串中的所有单词。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
请你返回一个反转 s 中单词顺序并用单个空格相连的字符串。
说明：

输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
反转后单词间应当仅用一个空格分隔。
反转后的字符串中不应包含额外的空格。

示例1：

输入：s = "the sky is blue"

输出："blue is sky the"

示例2：

输入：s = "hello world"

输出："world hello"

解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

这个题也经常出现在很多面试题中，我记得曾经见过有个题是这样出的，要你按照同样的方式反转“ I love youzan”。这个题的关键在于如何处理单词。
本题难度并不大，所以我们的重点就是从多种角度来分析该问题，

方法1：使用语言提供的方法来解决

Java、Python、C++等很多语言提供了相关的特性，因此我们可以首先使用语言的特性来实现：
很多语言对字符串提供了 split（拆分），reverse（反转）和 join（连接）等方法，因此我们可以简单的调用内置的 API 完成操作：

使用 split 将字符串按空格分割成字符串数组；
使用 reverse 将字符串数组进行反转；
使用 join 方法将字符串数组拼成一个字符串。

如图：

public String reverseWords(String s) {
    if (s == null || s.length() == 0) {
        return s;
    }
    // 除去开头和末尾的空白字符，记住这个操作
    s = s.trim();
    // 正则匹配连续的空白字符作为分隔符分割
    List<String> wordList = Arrays.asList(s.split("\\s+"));
    Collections.reverse(wordList);
    return String.join(" ",wordList);
}

C里没有提供类似的函数来调用，我们就不写了。
上面这种方式，在面试的时候，一般也不会让用，所以，我们还是看下面的方式：

方法2：自己实现上述功能

对于字符串可变的语言，就不需要再额外开辟空间了，直接在字符串上原地实现。在这种情况下，反转字符和去除空格可以一起完成。

实现方法：

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) {
        int left = 0, right = s.length() - 1;
        // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        // 去掉字符串末尾的空白字符
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        // 将字符串间多余的空白字符去除
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);

            if (c != ' ') {
                sb.append(c);
            } else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }

            ++left;
        }
        return sb;
    }

    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);
        }
    }

    public void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0, end = 0;

        while (start < n) {
            // 循环至单词的末尾
            while (end < n && sb.charAt(end) != ' ') {
                ++end;
            }
            // 翻转单词
            reverse(sb, start, end - 1);
            // 更新start，去找下一个单词
            start = end + 1;
            ++end;
        }
    }
}

2 验证回文串

LeetCode.125. 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。
回文问题在链表中是重点，在字符串中同样是个重点。当初我去美团面试第一轮技术面的第一个算法题就是让写判断字符串回文的问题。这个本身还是比较简单的，只要先转换成字符数组，然后使用双指针方法从两头到中间比较就行了。也许是过于简单了吧，面试时经常被加餐，例如LeetCode里的两道题。一个是普通的验证回文串，第二个是找最长的子回文串。第二个问题需要动态规划等技术，有点难度，我们到高级算法里再看，这里先看一下基本的。

示例1：

输入: "A man, a plan, a canal: Panama"

输出: true

解释："amanaplanacanalpanama" 是回文串

示例2：

输入: "race a car"

输出: false

解释："raceacar" 不是回文串

这个题我们可以有多种思路，最简单的方法是对字符串 s 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串 sgood 中。这样我们只需要判断 sgood 是否是一个普通的回文串即可。
如果不使用语言的特性，我们可以使用双指针思想来处理。
初始时，左右指针分别指向 sgood 的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明 sgood 时回文串。

public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        int n = sgood.length();
        int left = 0, right = n - 1;
        while (left < right) {
            if (sgood.charAt(left) != sgood.charAt(right)) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
}

3 字符串中的第一个唯一字符

LeetCode387. 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

s = "leetcode"

返回 0

s = "loveleetcode"

返回 2

提示：你可以假定该字符串只包含小写字母。
我们可以对字符串进行两次遍历，在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回 -1。

public int firstUniqChar(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    Map<Character,Integer> map = new HashMap<>();
    for(int i=0;i<s.length();i++){
        char ch = s.charAt(i);
        map.put(ch,map.getOrDefault(ch,0)+1);
    }
    for (int i = 0; i < s.length(); ++i) {
        if (map.get(s.charAt(i)) == 1) {
            return i;
        }
    }
    return -1;
}

4 判定是否互为字符重排

这是一道典型的看似吓人，其实很简单的问题。
LeetCode242 给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例1：

输入: s1 = "abcadfhg", s2 = "bcafdagh"

输出: true

示例2：

输入: s1 = "abc", s2 = "bad"

输出: false

这个题第一眼看，感觉是个排列组合的题目，然后如果使用排列的算法来处理，难度会非常大，而且效果还不一定好。用简单的方式就能解决。
第一种方法：将两个字符串全部从小到大或者从大到小排列，然后再逐个位置比较，这时候不管两个原始字符串是什么，都可以判断出来。代码也不复杂：

public boolean checkPermutation(String s1, String s2) {
    // 将字符串转换成字符数组
    char[] s1Chars = s1.toCharArray();
    char[] s2Chars = s2.toCharArray();
    // 对字符数组进行排序
    Arrays.sort(s1Chars);
    Arrays.sort(s2Chars);
    // 再将字符数组转换成字符串，比较是否相等
    return new String(s1Chars).equals(new String(s2Chars));
}

注意这里我们使用了不同语言的排序函数，你是否记得我们在数组一章提到过这个方法必须牢记。
第二种方法：使用Hash，注意这里我们不能简单的存是否已经存在，因为字符可能在某个串里重复存在例如"abac"。我们可以记录出现的次数，如果一个字符串经过重新排列后，能够变成另外一个字符串，那么它们的每个不同字符的出现次数是相同的。如果出现次数不同，那么表示两个字符串不能够经过重新排列得到。
这个代码逻辑不复杂，但是写起来稍微长一点：

public boolean checkPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        char[] s1Chars = s1.toCharArray();
        Map<Character, Integer> s1Map = getMap(s1);
        Map<Character, Integer> s2Map = getMap(s2);
        for (char s1Char : s1Chars) {
            if (!s2Map.containsKey(s1Char) || (int)s2Map.get(s1Char) != (int)s1Map.get(s1Char)) {
                return false;
            }
        }
        return true;
    }

    // 统计指定字符串str中各字符的出现次数，并以Map的形式返回
    private Map<Character, Integer> getMap(String str) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = str.toCharArray();
        for (char aChar : chars) {
            map.put(aChar, map.getOrDefault(aChar, 0) + 1);
        }
        return map;
    }