algorithm notes: leetcode#344 reverse string

Problem

Write a function that takes a string as input and returns the string reversed.

Example 1:

Input: "hello"
Output: “olleh”

Example 2:

Input: "A man, a plan, a canal: Panama"
Output: “amanaP :lanac a ,nalp a ,nam A”

Solution 1

Analysis

Use two pointers i,j. i iterates characters from left to the center and j iterates from right to the center, then exchange the values i and j points at.

Python implenmentation

1
2
3
4
5
6
7
8
9
10
11
12
13

class :
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        s = list(s)
        i, j = 0, len(s) - 1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1
        return "".join(s)

Java implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class  {
    public String reverseString(String s) {
        char[] ns = s.toCharArray();
        int i = 0;
        int j = ns.length - 1;
        
        while(i < j){
            char t = ns[i];
            ns[i] = ns[j];
            ns[j] = t;
            i ++;
            j --;
        }
        
        return new String(ns);
    }
}

Time complexity

O(n).

Space complexity

O(n).

Solution 2

Analysis

Iterate characters in string s backwards.

Python implementation

1
2
3
4
5
6
7

class (object):
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        return s[::-1]

Java implementation

1
2
3
4
5

class  {
    public String reverseString(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

Time complexity

O(n).

Space complexity

O(1).

Link

344. Reverse String
(中文版) 算法笔记: 力扣#344 反转字符串