字符串经典基础面试题（算法村第十二关白银挑战）

反转问题

反转字符串

344. 反转字符串 - 力扣（LeetCode）

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

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

对撞双指针

public void reverseString(char[] s)
{
    int left = 0;
    int right = s.length - 1;

    while (left < right)
    {
        char t = s[left];
        s[left] = s[right];
        s[right] = t;

        left++;
        right--;
    }
}

k个一组反转

541. 反转字符串 II - 力扣（LeetCode）

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 104
• s 仅由小写英文组成
• 1 <= k <= 104

解

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

public String reverseStr(String s, int k)
{
    char[] charArr = s.toCharArray();

    for (int i = 0; i < s.length(); i += 2 * k)
    {
        //反转的左边界
        int reverseLeft = i;
        //反转的右边界
        int reverseRight = Math.min(i + k, s.length()) - 1;
        //开始反转
        reverse(charArr, reverseLeft, reverseRight);
    }

    return new String(charArr);
}

public void reverse(char[] s, int left, int right)
{
    while (left < right)
    {
        char t = s[left];
        s[left] = s[right];
        s[right] = t;

        left++;
        right--;
    }
}

仅仅反转字母

917. 仅仅反转字母 - 力扣（LeetCode）

给你一个字符串 s ，根据下述规则反转字符串：

• 所有非英文字母保留在原有位置。
• 所有英文字母（小写或大写）位置反转。

返回反转后的 s 。

示例 1：

输入：s = "ab-cd"
输出："dc-ba"

示例 2：

输入：s = "a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"

示例 3：

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

对撞双指针+交换

public String reverseOnlyLetters(String s)
{
    char[] charArr = s.toCharArray();
    int left = 0;
    int right = s.length() - 1;

    while (left < right)
    {
        //找到左边未反转的第一个字母
        while (left < right && !Character.isLetter(charArr[left]) )
            left++;

        //找到右边未反转的第一个字母
        while (left < right && !Character.isLetter(charArr[right]) )
            right--;

        if (left > right)
            break;

        //交换
        char t = charArr[left];
        charArr[left] = charArr[right];
        charArr[right] = t;

        //更新指针
        left++;
        right--;
    }

    return new String(charArr);
}

反转字符串中的单词

151. 反转字符串中的单词 - 力扣（LeetCode）

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

**进阶：**如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

倒着遍历

倒着遍历，每次取出其中的单词，加入 ans 中即可

public String reverseWords(String s)
{
    StringBuilder ans = new StringBuilder();

    //从后往前遍历找单词
    for(int i = s.length() - 1; i >= 0; i--)
    {
        //跳过空格
        while (i >= 0 && s.charAt(i) == ' ')
            i--;

        if (i < 0)
            break;

        int end = i;    //末尾单词
        int start;      //单词的首字母

        //寻找单词首字母
        while (i >= 0 && s.charAt(i) != ' ')
            i--;
        start = i + 1;

        //往 ans 中添加空格和单词
        ans.append(' ');
        ans.append(s, start, end + 1);	//添加指定子串（末尾索引取不到）
    }

    //转换 ans 成字符串，并调用 trim() 方法除去前导空格（末尾的也能去除）
    return ans.toString().trim();
}

验证回文串

125. 验证回文串 - 力扣（LeetCode）

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

输入：s = " "
输出：true

对撞双指针

public boolean isPalindrome(String s)
{
    s = s.toLowerCase();

    char[] chars = s.toCharArray();
    int left = 0;
    int right = s.length() - 1;

    while (left < right)
    {
        while (left < right && !Character.isLetterOrDigit(chars[left]))
                left++;

        while (left < right && !Character.isLetterOrDigit(chars[right]))
                right--;

        if (left > right)
            break;

        if (chars[left] != chars[right])
            return false;

        left++;
        right--;
    }

    return true;
}

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

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

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

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

提示:

• 1 <= s.length <= 105
• s 只包含小写字母

HashMap

public int firstUniqChar(String s)
{
    char[] chars = s.toCharArray();
    HashMap<Character, Integer> hashMap = new HashMap<>();

    for (char ch : chars)
    {
        int count = hashMap.getOrDefault(ch, 0);
        hashMap.put(ch, count + 1);
    }

    for (int i = 0; i < hashMap.size(); i++)
        if(hashMap.get(chars[i]) == 1)
           return i;

    return -1;
}

有效的字母异位词

242. 有效的字母异位词 - 力扣（LeetCode）

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

**注意：**若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104
• s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

排序后再比较

public boolean isAnagram(String s, String t)
    {
        if(s.length() != t.length())
            return false;

        char[] chars_s = s.toCharArray();
        Arrays.sort(chars_s);

        char[] chars_t = t.toCharArray();
        Arrays.sort(chars_t);

        return Arrays.equals(chars_s, chars_t);
    }

HashMap

可以对付进阶要求

public boolean isAnagram(String s, String t)
{
    if(s.length() != t.length())
        return false;

    char[] chars_s = s.toCharArray();
    HashMap<Character, Integer> hashMap_s = new HashMap<>();

    for (char ch : chars_s)
    {
        int count = hashMap_s.getOrDefault(ch, 0);
        hashMap_s.put(ch, count + 1);
    }

    char[] chars_t = t.toCharArray();
    HashMap<Character, Integer> hashMap_t = new HashMap<>();

    for (char ch : chars_t)
    {
        int count = hashMap_t.getOrDefault(ch, 0);
        hashMap_t.put(ch, count + 1);
    }

    for (int i = 0; i < hashMap_s.size(); i++)
        if (!Objects.equals(hashMap_s, hashMap_t))
            return false;

    return true;
}

优化

从3次循环降为2次循环

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;
        
        Map<Character, Integer> table = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) 
        {
            char ch = s.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) + 1);
        }
        
        for (int i = 0; i < t.length(); i++)
        {
            char ch = t.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) - 1);
            
            if (table.get(ch) < 0) 
                return false;
        }
        
        return true;
    }
}