This is the ninth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Flip word order

Offer 58-i. Flip the word order

Difficulty: Easy

Topic: leetcode-cn.com/problems/fa…

Enter an English sentence and flip the order of the words in the sentence, but the order of the characters in the words remains the same. For simplicity, punctuation marks are treated like ordinary letters. For example, if you enter “I am a student.”, “student. A am I” is displayed.

Example 1:

Input: "The sky is blue" Output:" Blue is sky the"Copy the code

Example 2:

Type: "Hello world! "Output: "world! "Hello" explanation: The input string can contain extra space before or after it, but the reversed character cannot.Copy the code

Example 3:

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

Description:

  • No space characters make up a word.
  • The input string can contain excess space before or after it, but the reversed character cannot.
  • If there is extra space between two words, reduce the space between the inverted words to just one.

Answer key

Method one uses the API

  • Trim () removes Spaces at both ends of the string
  • Split (“) Splits Spaces into arrays
  • Filter () filters Spaces in the array
  • Reverse () Inverts the array
  • Join (“) is bounded by Spaces, and the array is transformed into a string
 / * * *@param {string} s
  * @return {string}* /
 var reverseWords = function (s) {
   let str = s.trim().split(' ').filter(item= >item ! =' ').reverse().join(' ');
   return str;
 };
Copy the code
  • Time complexity: O(N)
  • Space complexity: O(N)

Method two double pointer

Steps:

  • Discard the first and last Spaces, and walk through the string s from back to front, recording the left and right index boundaries I and j
  • Each time a word boundary is determined, the word is put into the array RES
  • The array res is turned into a string
 var reverseWords = function (s) {
   // 1. Remove the first and last Spaces
   s = s.trim();
 ​
   let j = s.length - 1,
     i = j;
   let res = [];
 ​
   while (j >= 0) {
     while (i >= 0&& s[i] ! = =' ') i--;// Search for Spaces
     res.push(s.slice(i + 1, j + 1)); // Add words
     while (j >= 0 && s[i] === ' ') i--; // Skip Spaces
     j = i; // j indicates the next word
   }
   return res.join(' '); // Convert the array to a string
 };
Copy the code
  • Time complexity: O(N)
  • Space complexity: O(N)

Left rotation string

Offer 58-ii. Left rotate string

Difficulty: Easy

Topic: leetcode-cn.com/problems/zu…

The left rotation operation of a string transfers the preceding characters to the end of the string. Define a function that performs the left rotation of a string. For example, if you input the string “abcdefg” and the number 2, the function will return “cdefgab” as a result of a left rotation of two digits.

Example 1:

Input: s = "abcdefg", k = 2 Output: "cdefgab"Copy the code

Example 2:

Input: s = "lrloseumgh", k = 6 output: "umghlrlose"Copy the code

Limit: 1 <= k < s.length <= 10000

Answer key

Method a string concatenation

 / * * *@param {string} s
  * @param {number} n
  * @return {string}* /
 var reverseLeftWords = function (s, n) {
   let str = s.substring(n) + s.substring(0, n);
   return str;
 };
Copy the code
  • Time complexity: O(N)
  • Space complexity O(N)

Method 2 list traversal concatenation

This approach can be used if an API is not allowed in the interview. The steps are as follows:

  • Create an array res
  • Store the value after n+1 in res
  • The first to n characters are then stored in the RES
  • The array RES turns to a string
 var reverseLeftWords = function (s, n) {
   const res = [];
   for (let i = n; i < s.length; i++) {
     res.push(s[i]);
   }
   for (let i = 0; i < n; i++) {
     res.push(s[i]);
   }
   return res.join(' ');
 };
Copy the code
  • Time complexity: O(N)
  • Space complexity: O(N)

Practice daily! The front end small adorable new one, hope can point to like ~