SoFunction
Updated on 2025-03-10

Summary of seven solutions to invert strings in Python

Difficulty of the question

Simple

Question description

Write a function that inverts the input string. Enter a string as a character arraysThe form is given.

Do not allocate additional space to other arrays, you must modify the input array in place and useO(1)extra space to solve this problem.

Example

Example 1

enter：s = ["h","e","l","l","o"]Output：["o","l","l","e","h"]

Example 2

enter：s = ["H","a","n","n","a","h"]Output：["h","a","n","n","a","H"]

Prompt information

  • 1 <= <= 105
  • s[i]They are all printable characters in the ASCII code table.

Solution 1: Double pointer

class Solution:
    def reverseString(self, s: List[str]) -&gt; None:
        """
        Do not return anything, modify s in-place instead.
        """
        # Define left and right pointers        left, right = 0, len(s) - 1
        while left &lt; right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
  • Double pointer concept: Use two pointers to point to the starting position and end position of the string respectively, and realize the inversion of the string by swapping the elements pointed by the pointer. This approach is very common when dealing with problems that require both ends on arrays or strings.
  • Simultaneous assignment characteristics of Python：s[left], s[right] = s[right], s[left]This writing method can assign values ​​to two variables at the same time without the need for intermediate variables. Python will first calculate the value on the right side of the equal sign, and then assign the value to the variable on the left side of the equal sign. In this process, actually, a containings[right]ands[left]tuple ofs[left]ands[right]。

Solution 2: Stack structure

class Solution:
    def reverseString(self, s: List[str]) -&gt; None:
        """
         Do not return anything, modify s in-place instead.
         Modify it in place without returning s, and directly reverse the s operation!
         """
        stack = []        # Define empty stack[]        for char in s:    # traverse all characters in s from the beginning            (char)  # Use .append(xxx) to implement it        # Implements the structure characteristics of s into the stack and use the stack        # The stack is first put and then the stack is released, and the inversion is achieved        # for i in len(s): len(s) is a number, length!  for a range        for i in range(len(s)):
            s[i] = ()  # i specifies the s[i] position for modification, .pop is a stack operation
  • Concept and operation of stack: The stack is a data structure that followsLater in and first out（LIFO) principle. In this solution, first push the characters in the string into the stack in sequence, then pop the characters from the stack and overwrite the corresponding position of the original string to achieve inversion. Use lists to simulate stack operations..append()Method is used to push elements onto the stack (at the end of the list),.pop()Methods are used to pop up the top element (element at the end of the list).
  • Structural characteristics of the stack:First in, first in, first in, last outJust right for reversal operation!

Solution 3: range function

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        n = len(s)
        for i in range(n // 2):
            s[i], s[n - i - 1] = s[n - i - 1], s[i]
  • Use of range function: The range function can generate a sequence of integers, such as range(n // 2) to generate a sequence of integers from 0 to half of the string length, which is used to traverse the first half of the string. Then i and n-1-i are the corresponding positions to be exchanged.
  • Getting and indexing string length:

Solution 4: reversed function

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = reversed(s)

What is involved in this codereversedDetailed explanation of functions and slice operations:

1. Reversed function

  • effect：

    • reversedIs a built-in function in Python that takes an iterable object as a parameter and returns an inverted iterator. This iterator can traverse elements of the input iterable object, but the order is reversed.
    • For example, for list[1, 2, 3]，reversed([1, 2, 3])It will return an iterator, and when it traverses this iterator, it will get it in turn3、2、1。

  • Features：

    • reversedThe function does not directly modify the original iterable object, but returns a new iterator. If you want to get the specific content after inversion, you can convert it into specific data structures such as lists, tuples, etc.
    • For example,list(reversed([1, 2, 3]))Will get[3, 2, 1]。

2. Slicing operation

  • Basic concepts：

    • In Python, slices are an operation used to extract a portion of elements from a sequence (such as lists, strings, tuples, etc.). It defines the part to be extracted by specifying the start index, the end index, and the step size.
    • The syntax of slice issequence[start:stop:step],instartis the starting index (default is 0),stopis the end index (excluding the elements at that index),stepis step size (default is 1).
    • For example, for listmy_list = [0, 1, 2, 3, 4, 5]，my_list[1:4]Will get[1, 2, 3]。

  • Function in code：

    • s[:]is a special slice operation that represents the entire sequencesPerform slices. The function here is toreversed(s)The returned inverted iterator is converted to a list (or other iterable object, depending onsand assign it tos, thereby realizing in-situ modifications。
    • It is equivalent to replacing all elements in the original sequence with the inverted content, achieving the purpose of inverting strings (or lists, etc.).

Why is the code written like this

  • first,reversed(s)Returns an inverted iterator, which containssThe order of inversion of elements in it.
  • Then, throughs[:] = reversed(s), convert this inverted iterator into a specific data structure (usually a list), and assign it tosthe entire slice. The advantage of this is that it can be modified in places, without creating a new list to store the inverted results, saving memory space.
  • At the same time, this writing method is concise and clear, and uses the powerful functions of Python's built-in functions and slice operations to achieve the inversion of strings (or lists, etc.) in an efficient way.

Solution 5: Slice

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = s[::-1]

Let's understand the knowledge points involved in this code in a simple way.

1. String slice

Imagine a string is like a beautiful string of beads, each representing a character. String slices are like a tool to select a portion of the beads from this bead.

  • Normal slices, for examples[start:end:step]：

    • startIt is where you start to choose the beads.
    • endIt is the position where you stop selecting the beads (but not including the beads at this position).
    • stepIt is the interval between each time you choose beads.
    • For examples[2:5]It is like starting from the third position of this bead and getting to the bead before the fifth position.

  • Special slicess[::-1]：

    • There is no starting and ending position specified here, which means taking from the beginning of the string to the end.
    • The step size is-1, it's like you start at the end of the string, taking one step forward each time, selecting beads in turn, and going all the way to the beginning of the string. So this gives you a reversed string.

2. Assign to s[:]

Imagine nowsIt's a box with beads.s[:]Indicates all beads in the entire box. Bundles[::-1]Assign tos[:], it is like replacing all the beads in the original box with the reversed beads obtained by special slicing. This enables the order of beads in the original box to be reversed without creating a new box (without taking up extra space).

So the purpose of this code is to invert the given string (actually a list of characters) in place by cleverly using string slices and assignment operations.

  • Key points of knowledge：
    • Advanced usage of string slicing: Slicing operations[::-1]It means starting from the end of the string, moving forward one step each time until the beginning of the string, thus obtaining the inverted string. This slicing syntax is very powerful and can be used to quickly extract part of a string, skip specific elements, etc. Here, by assigning the slice result tos[:], implements in-place inversion of strings.

Solution 6: List deduction

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = [s[i] for i in range(len(s) - 1, -1, -1)]
  • Key points of knowledge：
    • Principles of list comprehension: List comprehension is a concise syntax for quickly generating lists. In this solution,[s[i] for i in range(len(s) - 1, -1, -1)]Generates a list of characters from the end of the string to the beginning. Add each character to the list by traversing the index that subtracts from string length by 1 to 0. Then, overwrite the original string by slicing assignment to invert.
    • Reverse traversal of indexes：range(len(s) - 1, -1, -1)It means that starting from the string length minus 1, decrementing 1 at a time until -1 (excluding -1), implementing a reverse traversal of the string index.

The following is a detailed explanation of this solution idea, including the grammatical knowledge involved:

1. Principles of list comprehension

  • Basic concepts：

    • List comprehension is a concise syntax for quickly generating new lists. Its basic form is[expression for item in iterable if condition],inexpressionIt's for everyitemOperations performed,iterableis an iterable object.if conditionis an optional filter condition.
    • For example,[i * 2 for i in range(5)]A include will be generated0, 2, 4, 6, 8list. Here's rightrange(5)Each integer generated is multiplied by 2.

  • Application in this question：

    • [s[i] for i in range(len(s) - 1, -1, -1)]The purpose of this list comprehension is to generate a reversed character list.
    • s[i]Indicates the original stringsThe index isicharacters.
    • range(len(s) - 1, -1, -1)is a sequence of integers that starts from the last index of the string and decrements to the first index (excluding -1). This implements a reverse traversal of string indexes.

2. Reverse traversal of indexes

  • rangeFunction parameter explanation：

    • range(len(s) - 1, -1, -1)middle,len(s) - 1is the starting value, indicating the last index of the string.
    • -1It is the end value, indicating that you want to traverse to the previous position with index 0. Since the index starts from 0, the position -1 is not included.
    • The last one-1is the step size, indicating decrement by 1 each time.

  • The effect of reverse traversal：

    • Through this reverse traversal, each character in the string can be taken in sequence, starting from the last character and ending with the first character. This allows you to build a list of inverted characters.

3. Slice assignment achieves inversion

  • s[:]The role of：
    • s[:]Indicates slice operations on the entire string (actually a list of characters). The purpose here is to overwrite the newly generated inverted character list on the original string to achieve in-place inversion.
    • It is equivalent to replacing the original string with the newly generated inverted character list.

The design idea of ​​this solution is to use list derivation to quickly generate the inverted character list, and then overwrite it on the original string by slice assignment, thereby achieving string inversion without using extra space. This approach demonstrates the flexibility and power of list comprehension and slice operations in Python.

Solution 7: reverse() function

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s_list = list(s)
        s_list.reverse()
        s[:] = s_list
  • Key points of knowledge：
    • reverse method of list: There is one listreverseMethod, you can reverse the list in place. In this solution, first convert the input string into a lists_list, and then calls_list.reverse()Reverse the list in place. Finally, convert the inverted list back to the string and overwrite the original string by slicing assignment to achieve inversion.
    • Type conversion：list(s)Convert a string to a list so that you can use the list method to operate. Then, when converting the inverted list back to a string, assign values ​​through slicess[:] = s_listImplement in-situ modification of strings.

To sum up, these solutions demonstrate many different programming techniques and usage of data structures in Python, and by skillfully leveraging this knowledge, string inversion problems can be solved efficiently.

Replenish:
Tuple:In Python, tuples (Tuple) are immutable ordered sequences that are similar to lists, but with some important differences. Here is a detailed introduction to tuples:

Tuple definition

  • Tuples use brackets()to indicate that the elements are separated by commas. For example:my_tuple = (1, 2, 3)Defines a tuple containing three integer elements.
  • Tuples can also be defined without using brackets, but are directly separated by commas, for example:my_tuple = 1, 2, 3It is equivalent to the above definition.

Characteristics of tuples

  • Immutability: Once a tuple is created, its elements cannot be modified, deleted, or replaced. This means that tuples provide a guarantee of data integrity, suitable for storing sets of data that should not be changed.
  • Orderful: The elements in the tuple are ordered and can be accessed through the index. Like lists, the index of a tuple starts at 0, e.g.my_tuple[0]The first element in the tuple is accessed.

The role of simultaneous assignment

  • exist s[left], s[right] = s[right], s[left]In this statement that is assigned simultaneously, the right side of the equal signs[right], s[left]In fact, it forms a temporary tuple. Python will first calculate the value of this tuple, that is, gets[right]ands[left]and combine them into a tuple(The value of s[right], the value of s[left])。
  • Python will then assign the elements in this tuple to the variable on the left side of the equal sign in order, respectively.s[left]ands[right]. This method concisely implements the exchange of values ​​of two variables without the need to temporarily store values ​​using intermediate variables.

Why use the concept of tuples

  • Simplicity: Using tuples can complete the assignment of multiple variables in a line of code, making the code more concise and easy to read. Compared to using intermediate variables to implement exchange, this method is more intuitive and efficient.
  • Atomicity: The immutability of tuples ensures atomicity during the assignment process. That is, the entire assignment operation is an inseparable whole, either all succeed or all fail. There is no intermediate state, thus avoiding some potential errors and inconsistencies.
  • Consistency with Python syntax: Tuples and tuple-like structures are widely used in Python's syntax design. For example, a function can return multiple values, but in fact it returns a tuple. In many other scenarios, tuples are also used to represent a set of related values. Therefore, the use of tuple concepts in simultaneous assignment is consistent with Python's overall syntax style and programming habits.

Tuples have many application scenarios in Python, and the following are some common examples:

Data packaging and unpacking

  • Multiple values ​​return: The function can return multiple values, which will be automatically packaged into a tuple. For example:
def get_name_and_age():
    return "Alice", 25

name, age = get_name_and_age()
print(name)  
print(age)

In this example,get_name_and_ageThe function returns a tuple containing the name and age, and then assigns the values ​​in the tuple to each of the multivariate assignments.nameandagevariable.

  • Data exchange: As mentioned above, the value of the exchange variable is used to concisely implement the exchange operation without the help of intermediate variables.
a = 5
b = 10
a, b = b, a
print(a)  
print(b)

Function parameter passing

  • Fixed parameter order: When a function needs to receive multiple parameters, and the order and meaning of these parameters are fixed, the parameters can be passed using tuples. For example, for a function that draws a graph, it may be necessary to receive a tuple of coordinate points as parameters.
def draw_point(point):
    x, y = point
    print(f"Draw points ({x}, {y})")

point = (3, 4)
draw_point(point)
  • Variable parameters: In function definition, tuples can be used to receive an uncertain number of parameters. By adding the parameters*, multiple parameters can be collected into a tuple.
def print_args(*args):
    for arg in args:
        print(arg)

print_args(1, 2, 3, "hello")

Data protection and immutability

  • Prevent accidental data modification: Tuples are a great choice when it comes to ensuring that the data is not modified. For example, configuration information, constant data, etc. may be stored using tuples to prevent accidental modification of these data in other parts of the program.
COLORS = ('red', 'green', 'blue')
# The following code throws an error because the tuple is immutable# COLORS[0] = 'yellow'

Elements in a data structure

  • Dictionary keys: Tuples can be used as keys to dictionaries because they are immutable. This is useful in situations where multiple values ​​are required as dictionary keys.
student_info = {('Alice', 25): 'excellent', ('Bob', 22): 'good'}
print(student_info[('Alice', 25)])
  • Elements of the collection: Tuples can also be used as elements of collections, also because of their immutability. Elements in a collection must be unique, and using tuples as elements can facilitate storage and manipulation of multiple related values.
my_set = {(1, 2), (3, 4), (1, 2)}
print(my_set)

Parallel iteration

  • Multiple iterable objects can be iterated at the same time and their elements are combined into tuples for processing. For example, iterate over two lists simultaneously and print the corresponding elements.
names = ["Alice", "Bob", "Charlie"]
ages = [25, 30, 35]
for name, age in zip(names, ages):
    print(f"{name} is {age} years old.")

Database operations

  • When interacting with a database, the query results are usually returned as tuples. Each tuple represents a row of data, with elements corresponding to columns in the query result.
import sqlite3

conn = ('')
cursor = ()
("SELECT name, age FROM students")
results = ()
for row in results:
    print(row)  
()

These are just some common application scenarios for tuples in Python. In fact, tuples have wide applications in various programming tasks and data processing scenarios. Its immutability and simplicity make it a very useful data structure in Python programming.

The following is correctrangeDetailed introduction to the function:

1. Characteristics of range function

  • Generate an integer sequence：

    • rangeFunctions are mainly used to generate a sequence of integers. It can accept one, two or three parameters, corresponding to different usages.
    • When only one parameter is passednhour,range(n)Will generate from0arriven - 1sequence of integers. For example,range(5)Will generate0, 1, 2, 3, 4。
    • When two parameters are passedstartandendhour,range(start, end)Will generate fromstartarriveend - 1sequence of integers. For example,range(2, 5)Will generate2, 3, 4。
    • When passing in three parametersstart、endandstephour,range(start, end, step)Will generate fromstartStart, each timestep, until less thanendsequence of integers. For example,range(1, 10, 2)Will generate1, 3, 5, 7, 9。

  • Efficiency：

    • rangeAn object is a "lazy evaluation" sequence type. It does not generate all integers at once, but generates them one by one when needed. This makes it very efficient when dealing with large numbers of sequences of integers, especially when memory constrained.

  • Iterability：

    • rangeObjects are iterable and can beforUse directly in a loop. For example:for i in range(5): print(i)Will print in turn0, 1, 2, 3, 4。

2. How to use range function

  • Basic usage：

    • As mentioned earlier, it is used to generate a sequence of integers and infortraversal in a loop.
    • For example:for i in range(3): print(f"{i + 1} loop")。

  • Combined with list comprehension：

    • It can be used in combination with list comprehensions to quickly generate lists. For example:new_list = [i * 2 for i in range(5)]A include will be generated0, 2, 4, 6, 8list.

  • As function parameter：

    • Some functions accept iterable objects as parameters.rangeThe generated sequence of integers can be used as parameters to these functions. For example,sum(range(1, 11))The sum of integers from 1 to 10 can be calculated.

III. Application scenarios of range function

  • Cycle control：

    • In case of a fixed cycle,rangeVery useful. For example, iterate over a list and process each element.
    • For example:my_list = [1, 2, 3, 4, 5]，for i in range(len(my_list)):You can traverse the index of the list to access and modify elements in the list.

  • Generate index sequences：

    • When you need to index the sequence, you can userangeGenerate index sequences. For example, in the example of string inversion, byrange(n // 2)Generates an index sequence for the first half of the string to exchange characters.

  • Step length control：

    • When it is necessary to traverse or generate a sequence according to a specific step size, you can use the third parameter to specify the step size. For example, generating an odd sequence can be usedrange(1, 10, 2)。

  • Combined with other data structures：

    • It can be used in combination with data structures such as lists, tuples, and collections to perform various operations. For example, when generating a list of integers in a specific range, or when performing slicing operations on an iterable object, you can userangeto determine the start and end positions of the slice.

Anyway,rangeFunctions are a very practical tool in Python. They have extensive applications in loop control, indexing operations, and sequence generation, which can improve the efficiency and readability of the code.

Space-time complexity analysis

The following are the analysis and comparison of the time and spatial complexity of these seven solutions:

1. Solution 1: Double pointer

  • Time complexity：

    • Since only half of the length of the string is traversed at once, the time complexity is O ( n ) O(n)O(n), wherenis the length of the string.

  • Space complexity：

    • Only two pointer variables were used, and there was no additional data structure, so the spatial complexity was O ( 1 ) O(1) O(1).

2. Solution 2: Stack structure

  • Time complexity：

    • Iterates over the string and puts the characters on the stack, then traverses over the string and assigns values. Iterates over the string twice in total, and the time complexity is O ( n ) O(n)O(n).

  • Space complexity：

    • A stack is used to store characters in a string. In the worst case, the entire string needs to be stored, so the space complexity is O ( n ) O(n)O(n).

3. Solution three: range function

  • Time complexity：

    • The same is to traverse half of the string for exchange operations, with the time complexity of O ( n ) O(n)O(n).

  • Space complexity：

    • No additional data structures were used, only a few variables were used, and the spatial complexity was O ( 1 ) O(1) O(1).

4. Solution 4: reversed function and slice

  • Time complexity：

    • The operation time complexity of creating an inversion iterator and performing slice assignment is O ( n ) O(n)O(n).

  • Space complexity：

    • reversedThe iterator returned by the function does not occupy extra space, the slice assignment is in-situ operation, and the space complexity is O ( 1 ) O(1) O(1).

5. Solution 5: Slice

  • Time complexity：

    • The time complexity of the slice operation itself can be considered O ( n ) O(n)O(n) because it involves traversing the string.

  • Space complexity：

    • The slice operation is modified in situ, without additional data structures, and the spatial complexity is O ( 1 ) O(1) O(1).

6. Solution 6: List deduction

  • Time complexity：

    • The time complexity of the list comprehension traversing string is O ( n ) O(n)O(n), plus the time complexity of slice assignment is O ( n ) O(n)O(n), and the overall time complexity is O ( n ) O(n)O(n).

  • Space complexity：

    • List comprehension creates a new temporary list, with the worst-case length ofn, but finally overwrite the original list by slice assignment, so the spatial complexity is a mixture of O ( n ) O(n) O(n) (temporary list taking up space) and O ( 1 ) O(1) O(1) (final space complexity). Considering the final in-place modification, the overall can be considered O ( 1 ) O(1) O(1) O(1).

7. Solution 7: reverse() function

  • Time complexity：

    • List ofreverseThe time complexity of the method is O ( n ) O(n)O(n).

  • Space complexity：

    • A new list is created and then sliced ​​assigns. The temporary list takes up space O ( n ) O(n)O(n), but it is finally modified on the spot. The overall space complexity can be considered O ( 1 ) O(1)O(1).

Comparative analysis：

  • Time complexity: The time complexity of the seven solutions is O ( n ) O(n) O(n), and there is little difference. However, in actual operation, there may be some subtle performance differences due to different operations. For example, methods such as double pointers, range functions, reversed functions and slices are relatively simple and direct, and may be slightly faster in some cases.

  • Space complexity: The spatial complexity of solutions 1, 3, 4, 5, and 7 are all O ( 1 ) O(1) O(1), because they are all modified in situ and no additional linear space is used. Solution 2 uses the stack, and the worst-case space complexity is O ( n ) O(n) O(n). Solution 6 creates a temporary list during the list derivation process. Although it is finally modified on site, it may occupy additional space during the process. The overall situation can also be considered O ( 1 ) O(1) O(1).

To sum up, when solving this problem, if the space requirements are high, you can prefer methods such as double pointers, range functions, reversed functions and slices with space complexity of O ( 1 ) O(1)O(1). If you pay more attention to the simplicity and readability of the code, you can choose the appropriate solution according to the specific situation.

Summarize

This is the end of this article about seven solutions to python inverting strings. For more related contents of python inverting strings, please search for my previous articles or continue browsing the following related articles. I hope everyone will support me in the future!