算法小试:反转字符串中的单词 III

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

示例 1:

输入:s = "Let's take LeetCode contest"
输出:"s'teL ekat edoCteeL tsetnoc"
示例 2:

输入: s = "God Ding"
输出:"doG gniD"

提示:

1 <= s.length <= 5 * 104
s 包含可打印的 ASCII 字符。
s 不包含任何开头或结尾空格。
s 里 至少 有一个词。
s 中的所有单词都用一个空格隔开。

解题思路
然后从头到尾遍历原字符串,直到找到空格为止,此时找到了一个单词,并能得到单词的起止位置。随后,根据单词的起止位置,可以将该单词逆序放到新字符串当中。如此循环多次,直到遍历完原字符串,就能得到翻转后的结果

// 额外空间
public static String reverseWords2(String s) {
    StringBuilder result = new StringBuilder();
    int len = s.length();
    int i = 0;
    while (i < len) {
        int start = i;
        //计算空格之前的索引
        while (i < len && s.charAt(i) != ' ') {
            i++;
        }
        // 翻转单个单词
        for (int j = start; j < i; j++) {
            result.append(s.charAt(start + i - j - 1));
        }
        //增加空格, i++
        while (i < len && s.charAt(i) == ' ') {
            i++;
            result.append(' ');
        }
    }
    return result.toString();
}

题外话
其实还有其他算法,只不过需要借助外部类方法StringUtils.join来合并字符串
双指针
仅供参考

public static String reverseWords(String s) {
    String[] arr = s.split(" ");
    // 多个单词自身翻转,双指针
    for (int i = 0; i < arr.length; i++) {
        String[] ns = arr[i].split("");
        // 双指针, 对换位置
        int n = ns.length;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            String tmp = ns[left];
            ns[left] = ns[right];
            ns[right] = tmp;
            left++;
            right--;
        }

        arr[i] = (StringUtils.join(ns));
    }
    return StringUtils.join(arr, " ");
}

你可能感兴趣的