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

The title

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:

  • Input stringsYou can include extra Spaces before, after, or between words.
  • Flipped words should be separated by a single space.
  • The flipped string should not contain additional Spaces.

Source: LeetCode link: leetcode-cn.com/problems/re…

Example:

Example 1:

Input: s = “The sky is blue” output:” Blue is sky the”

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.

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.

Implementation scheme 1: Use Java language features

Implementation steps:

  1. Cuts a string into an array of words through Spaces
  2. Invert words (by converting arrays to sets using the invert function of sets)
  3. Reconcatenate strings with Spaces
public String reverseWords(String s) {
    if (s == null || "".equals(s.trim())) {
        return "";
    }
    // Remove Spaces at both ends of the string
    s = s.trim();

    // Cut the array into arrays by Spaces
    String[] strings = s.split("\\s+");
    // Convert an array to a collection
    List<String> list = Arrays.asList(strings);
    // Reverse the set data
    Collections.reverse(list);
    // Collections are concatenated into strings by Spaces
    return String.join("", list);
}
Copy the code

Implementation scheme 2: array + double pointer

Implementation logic:

  1. Create a new array for temporary storage
  2. Create first and last Pointers
  3. Traverse the string in reverse order to locate the beginning and end index of the word
  4. Retrieves the string into a temporary array based on the start-stop index
  5. Restore the pointer and repeat the loop to locate the next word
  6. Generates a new string from the valid data in the new array
public String reverseWords2(String s) {
    s = s.trim();
    int len = s.length();

    if (s == null || len == 0) {
        return "";
    }
    char[] chars = new char[len];
    / / head
    int first = -1;
    / / the end
    int last = -1;
    // New array index
    int index = 0;
    // Find the index of the word in reverse order
    for (int i = len - 1; i >= 0; i--) {
        char c = s.charAt(i);
        //
        if(c ! =' ') {
            if (last == -1) {
                last = i;
            }
            if (i == 0) { first = i; }}else {
            if(last ! = -1) {
                first = i + 1; }}// Write the read word to the new array
        if (first >= 0 && last >= 0) {
            if (index > 0) {
                chars[index++] = ' ';
            }
            while (first <= last) {
                chars[index++] = s.charAt(first);
                first++;
            }
            // Restore the pointer
            first = last = -1; }}// Convert the resulting array to a string
    return String.valueOf(chars, 0, index);
}
Copy the code

Implementation scheme 3: double-ended queue

Implementation logic

  • Store each word in turn to the head of a double-ended queue
    • The character is stored in a buffer by traversing
    • When the end of the word is reached, the word in the buffer is placed in the head of the two-ended queue
  • To fetch a word from a two-ended queue: passString.joinJoin words with Spaces
public String reverseWords4(String s) {
    int left = 0, right = s.length() - 1;
    Deque<String> d = new ArrayDeque<String>();
    StringBuilder word = new StringBuilder();
    while (left <= right) {
        char c = s.charAt(left);
        if(c ! =' ') {
            word.append(c);
        } else {
            // Get to the end of the word
            if(word.length() ! =0) {
                // Add the word to the head of the queue
                d.offerFirst(word.toString());
                word.setLength(0);
            }
        }
        ++left;
    }
    if (word.length() > 0) {
        d.offerFirst(word.toString());
    }
    return String.join("", d);
}
Copy the code

Making the address

Case address

other

The majority of stubborn friends, if you read the article!! Please don’t be stingy with your comments!! If there is a better way to solve the problem or I solve the problem in the lack of place, the article writing is not good, I hope you can give me a comment or two!! Thank you all!!