This is the 26th day of my participation in the First Challenge 2022

First, write first

I heard you’re still writing a two-layer for loop to solve the sum of two numbers?

LeetCode 2: Sum of two numbers transfer gate: the median of two sorted arrays, “most” technical solution!

LeetCode 第 3 题 : Longest loop transport gate: Horse-and-cart algorithm to solve longest loop! Manacher

LeetCode 4 题 conversion of string to integer (ATOI) : Solve ATOI with “foolish old man removing mountains” method, think clever!

Continue solving LeetCode, the longest public prefix

One of LeetCode’s “most classic” algorithm problems: the sum of three numbers

The sum of the nearest three numbers, wonderful

LeetCode: Valid parentheses

Delete duplicates in LeetCode: delete duplicates in LeetCode

The container that holds the most water is the container that holds the most water

LeetCode 11 string multiplication: LeetCode string multiplication, what do you do?

LeetCode reverses the string. I’m cheating again!

Question 13: Reverse the word III in the string, for the interview, looking forward to your participation. “Use the utility in the API is recommended in the project. But if you Use it in an interview, You will definitely fail.”

Today’s topic

Given a string, you need to reverse the character order of each word in the string, while still preserving the Spaces and the original order of the words.

Example:

Input:"Let's take LeetCode contest"Output:"s'teL ekat edoCteeL tsetnoc" 
Copy the code

Note: In a string, each word is separated by a single space, and there are no extra Spaces in the string.

Three, the analysis

This topic, see one eye, feel a little difficult, I saw the topic, the thought is a string with English words, only recognize English words, then it is good to reverse the English words, then a look carefully, is a string composed of English words and space, only in this way, is simple, specific ideas mentioned in the diagram below:

Fourth, the problem solving

1. Quick way:

Time complexity: O(n) Still has to go through every word, after all

class Solution(object) :
	def reverseWords(self, s) :
		""" :type s: str :rtype: str """
		# Separate strings according to Spaces
		r_list = s.split("")
		
		# Reverse each word string in the list
		for i in range(len(r_list)):
			r_list[i] = r_list[i][::-1]
		
		# Connect each word in the list with ""
		result_s = "".join(r_list)
		return result_s
Copy the code

(1) Do you know how to slice /join? (A) More detailed introduction.

(2) split function

Python split((STR, num) slices the string by specifying a separator, and only the num substring is split if the num argument has a specified value. Parameter Description:

STR -- the delimiter. Defaults to all null characters, including Spaces, newlines (\n), tabs (\t), and so on. Num -- the number of splits.Copy the code

(3) Submit results

Test data: 30 groups running time: 32ms beat percentage :94.56%

2. Do it yourself?

Traversal, grouping are their own implementation, more trouble, first of all, the string according to the space for segmentation, into a word, and then in turn to deal with each word, after good processing also need to solve the merge into a string, equivalent to the need for three traversal.

Time complexity: O(n)

class Solution(object) :
	def reverseWords(self, s) :
		""" :type s: str :rtype: str """
		# Separate strings according to Spaces
		s = s + ' '
		r_list = []
		word = ' '
		flag = 0
		for i in s:
			ifi ! ="":
				word = word + i
				flag = 1
			else:
				if flag == 1:
					r_list.append(word)
					word = ' '
					flag = 0
		
		# Reverse each word string in the list
		for i in range(len(r_list)):
			r_list[i] = self.reverseString(r_list[i])
			
		# Connect each word in the list with ""
		result_s = ' '
		for i in range(len(r_list)):
			if i == len(r_list)-1:
				result_s = result_s + r_list[i]
				break
			result_s = result_s + r_list[i] + ""
		
		return result_s
	
	# leetcode12 implements its own string reversals
	def reverseString(self, s) :
		""" :type s: str :rtype: str """
		result = list(s)
		for i in range(len(result)//2):
			temp = result[len(result)-i-1]
			result[len(result)-i-1] = result[i]
			result[i] = temp
		return ' '.join(result)
Copy the code
  • Submit the results

Test data: 30 groups Running time: 204ms Beat percentage :2.89%

Although beat people are not many, but I have ideas, I am proud ~

Feel very cool, feel very hard, the reality is very cruel, have this feeling?

Five, the conclusion

Persistence and hard work: results.

Like to see the message forwarding, four support, the original is not easy. Ok, see you next time, I love the cat love technology, more love si si’s old cousin Da Mian ଘ(˙꒳˙)ଓ Di Di