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