串编辑

单词反转

151. 反转字符串中的单词 mid

剑指 Offer 58 - I. 翻转单词顺序

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

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

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

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

反转整个 s, 然后反转每个单词即可

class Solution {
    public String reverseWords(String s) {
        return String.join(" ", Arrays.asList(s.trim().split("\\s+")).reversed());
    }
}

class Solution {
    public String reverseWords(String s) {
        String[] arr = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = arr.length - 1; i >= 0; i--) {
            String ss = arr[i];
            if (!"".equals(ss)) sb.append(ss).append(" ");
        }
        return sb.toString().trim();
    }
}

344. 反转字符串 easy

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

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

class Solution {
    public void reverseString(char[] s) {
        int i = 0, j = s.length - 1;
        while (i < j) {
            swap(s, i++, j--);
        }
    }
}

345. 反转字符串中的元音字母 easy

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。

解法 双指针

class Solution {
    public String reverseVowels(String s) {
        char[] arr = s.toCharArray();
        Set<Character> set = Set.of('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');
        for (int i = 0, j = s.length() - 1; ; i++, j--) {
            while (i < j && !set.contains(arr[i])) i++;
            while (i < j && !set.contains(arr[j])) j--;
            if (i >= j) break;
            swap(arr, i, j);
        }
        return String.valueOf(arr);
    }

    private void swap(char[] arr, int i, int j) {
        char t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

557. 反转字符串中的单词 III easy

给定一个字符串 s，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

class Solution {
    public String reverseWords(String s) {
        return Arrays.stream(s.split(" "))
                .map(o -> new StringBuilder(o).reverse())
                .reduce(new StringBuilder(), (a, b) -> a.append(' ').append(b))
                .toString()
                .trim();
    }
}

编解码

394. 字符串解码 mid

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4]的输入。

解法 栈

用栈模拟递归，关键在于递归结果的保存，要想清楚在哪里递归

class Solution {
    public String decodeString(String s) {
        Deque<StringBuilder> stack = new ArrayDeque<>();
        Deque<Integer> multiStack = new ArrayDeque<>();
        StringBuilder prefix = new StringBuilder();
        int multi = 0;
        for (char c : s.toCharArray()) {
            if (c >= '0' && c <= '9') {
                multi = multi * 10 + c - '0';
            } else if (c == '[') {
                multiStack.push(multi);
                multi = 0;
                // 递，保存pre
                stack.push(prefix);
                prefix = new StringBuilder();
            } else if (c == ']') {
                // 归，将子串repeat然后拼到pre
                prefix = stack.pop().repeat(prefix, multiStack.pop());
            } else {
                prefix.append(c);
            }
        }
        return prefix.toString();
    }
}

区间编辑

848. 字母移位 mid

有一个由小写字母组成的字符串 s，和一个长度相同的整数数组 shifts。

我们将字母表中的下一个字母称为原字母的 移位 shift() （由于字母表是环绕的， 'z' 将会变成 'a'）。

例如，shift('a') = 'b', shift('t') = 'u', 以及 shift('z') = 'a'。 对于每个 shifts[i] = x ， 我们会将 s 中的前 i + 1 个字母移位 x 次。

返回 将所有这些移位都应用到 s 后最终得到的字符串 。

class Solution {
    public String shiftingLetters(String s, int[] shifts) {
        int n = shifts.length;
        int[] arr = Arrays.copyOf(shifts, n);
        // 后面的累加到前面
        for (int i = n - 2; i >= 0; i--) {
            arr[i] = (arr[i] + arr[i + 1]) % 26;
        }
        StringBuilder sb = new StringBuilder(s);
        for (int i = 0; i < n; i++) {
            char c = sb.charAt(i);
            c = (char) ('a' + (c - 'a' + arr[i]) % 26);
            sb.setCharAt(i, c);
        }
        return sb.toString();
    }
}