算法通关村——字符串反转问题解析

字符串反转问题

我们知道反转是链表的一个重要考点，反转同样是字符串的重要问题。字符串和链表在处理反转的方式上有相似的地方，一般都是运用双指针，一个指针从前找，一个指针从后找。具体的处理办法结合下面具体的题目来看：

1、反转字符串

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

示例：

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

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

这是最基本的反转问题，也是最简单的问题，使用双指针方法最直接。具体做法是：

将left 指向字符数组首元素，right指向字符数组尾元素
当left < right时：
- 交换s[left] 和 s[right]
- left指针向右移一位
- right指针向左移一位
当left>=right时，反转结束，返回字符数组

具体的java代码如下：

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 temp = s[left];
        s[left] = s[right];
        s[right] = temp;
    }
}

2、K个一组反转

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

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

示例1：

输入：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--;
    }
}

3、仅仅反转字母

LeetCode917. 给定一个字符串S，返回”反转后的”字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。

示例1：

输入：“ab-cd”

输出：“dc-ab”

示例2：

输入：“a-bC-dEf-ghIj”

输出：“j-Ih-gfE-dCba”

示例3：

输入：“Test1ng-Leet=code-Q!”

输出：“Qedo1ct-eeLg=ntse-T!”

这题的难点主要在需要反转的段的划分不均匀，也就是非字母的字符出现在字符串中的位置是随机的。可以考虑用以下两种方法来做：

方法1：使用栈

将s中的所有字母单独存入栈中，所以出栈等价于对字母反序操作。然后，遍历s的所有字符，如果是字母我们就选择栈顶元素输出，不是字母就输出s的字符。代码如下：

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从后往前遍历字符串，当需要字母时就使用它。代码如下：

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.isLetter(s.chatAt(i))) {
            while (!Character.isLetter(s.char)){
                j--;
            }
            ans.append(s.charAt(j--));
        } else {
            ans.append(s.chatAt(i));
        }
    }
    return ans.toString();
}

4、反转字符串里的单词

LeetCode151. 给你一个字符串，逐个反转字符串中的所有单词。

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

请你返回一个反转s中单词顺序并用单个空格相连的字符串。

说明：

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

示例：

输入：s = “the sky is blue”

输出：s = “blue is sky the”

在java语言中对字符串提供了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);
}

如果不使用语言自己的提供的方法，也可以完成这一题。

方法流程如下：

代码如下：

public static String reverseWords(String s) {
    StringBuilder sb = trimSpaces(s);

    // 翻转字符串
    reverse(sb, 0, sb.length() - 1);
    // 翻转每个单词
    reverseEachWord(sb);
    return sb.toString();
}

public static 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 static 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 static 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;
    }
}