This is the 28th day of my participation in the August Text Challenge.More challenges in August

Title description:

151. Flip the word in the string – LeetCode (leetcode-cn.com)

Given a string s, flip all the words in the string one by one.

A word is a string of non-space characters. Use at least one space in s to separate the words in the string.

Return a string that reverses the order of the words in s and concatenates them with a single space.

Description:

The input string s can contain extra Spaces before, after, or between words. Flipped words should be separated by a single space. The flipped string should not contain additional Spaces. Example 1:

Input: s = "The sky is blue" output:" Blue is sky the"Copy the code

Example 2:

Input: s = "hello world" Output: "world hello" Explanation: The input string can contain extra Spaces before or after the character, but the inverted character cannot.Copy the code

Example 3:

Input: s = "a good example" Output: "example good a" Explanation: If there is extra space between two words, reduce the space between the flipped words to only one.Copy the code

Example 4:

Input: s = "Bob Loves Alice" output: "Alice Loves Bob"Copy the code

Example 5:

Input: s = "Alice does not even like Bob "output:" Bob like even not does Alice"Copy the code

Tip:


  • 1 < = s . l e n g t h < = 1 0 4 1 <= s.length <= 10^4
  • sContains uppercase and lowercase letters, digits, and Spaces' '
  • s 中 There is at least oneThe word

 

Advanced:

Try the in situ solution using O(1)O(1)O(1) extra spatial complexity.

Thought analysis

Leveraging the language API

This is the easiest, and I’m sure most programming languages provide apis for similar basic operations, splitting strings, reversing strings, inserting strings, etc.

AC code

class Solution {
    fun reverseWords(s: String): String = 
        s.split("").filter { it.isNotBlank() }.asReversed().joinToString("")}Copy the code

The stack

We need to find the words first, after finding the words, we put them on the stack in order, using the principle of last in, first out, we take the first word from the stack is the last word, so as to achieve inversion.

AC code

class Solution {
    fun reverseWords(s: String): String {
        val stack = LinkedList<String>()

        var word = StringBuilder()
        // First iterates through the string and extracts the words onto the stack
        for (i in 0 until s.length) {
            if(s[i] ! =' ') {
                word.append(s[i])

                // Key criteria: when is the word pushed, if there is a space after the letter or the last letter
                if (i == s.lastIndex || s[i + 1] = =' ' ) {
                    stack.push(word.toString())
                    word = StringBuilder()
                }
            }
        }

        // Add elements and Spaces to the stack to form the inverted result
        val res = StringBuilder()
        while (stack.isNotEmpty()) {
            res.append(stack.pop())
            if (stack.isNotEmpty()) {
                res.append(' ')}}return res.toString()
    }
}
Copy the code

conclusion

Instead of using off-the-shelf apis to solve problems, using stacks is a good idea.

reference

Flip A word in a string – Flip a word in a string – LeetCode (leetcode-cn.com)

151. Flip Word in String – Flip Word in String – LeetCode (leetcode-cn.com)