leetcode Backtracking

leetcode 151题

Posted by franki on March 4, 2021

leetcode 151题 翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

说明：

  • 无空格字符构成一个 单词 。
  • 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

示例1:

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

示例2:

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

示例3:

输入："a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路

双指针

代码

const reverseWords = (s) => {
    let left = 0, right = s.length - 1;
    while (s.charAt(left) === " ") {
        left++;
    }
    while (s.charAt(right) === " ") {
        right--;
    }
    let word = "";
    const queue = [];
    while (left <= right) {
        if (word && s.charAt(left) === " ") {
            queue.unshift(word);
            word = "";
        } else if (s.charAt(left) !== " ") {
            word += s.charAt(left);
        }
        left++;
    }
    queue.unshift(word);
    return queue.join(" ");
};

复杂度分析

  • 时间复杂度: O(N))
  • 空间复杂度: O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS