【Leetcode 完整解答】344. Reverse String

有時間的話,可以看完正影片的解答。

Write a function that reverses a string. The input string is given as an array of characters s.

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Constraints:

Follow up: Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

解答:

在 python,長度為一的字串就是字元。

s 是個字串(str),Python 中字串的物件是唯讀的,不可變的。

但如果以 list (列表) 的方式傳,以 s = [‘H’, ‘e’, ‘l’, ‘l’, ‘o’] 舉例,列表中的 s[0] 是可以被改成小寫的 ‘h’ 的。

以 hello 為例,

s[0] , s[1] , s[2] , s[3] , s[4] = s[4] , s[3] , s[2] , s[1] , s[0]

其實也就相當於:

s[:] = s[::-1]

解答2 :

for i in range(len(s)//2):
    j = (len(s)-1)-i
    s[i], s[j] = s[j], s[i]

邏輯:

同樣以 hello 為例,先把位子0, 4的交換,再把 1, 3 的交換

邏輯:
i, j = 0, 4
s[i], s[j] = s[j], s[i]

i, j = 1, 3
s[i], s[j] = s[j], s[i]

可以觀察得出 i+j=4。

這時候我們再從頭看一遍程式。

for i in range(len(s)//2):

s 的長度之所以為原先的一半,是因為 i 和 j 的相加為 s 的長度,我們只要在前半部份跑過一遍, 全部字元就交換完畢。

再來看看 for 迴圈裡的第一行:

j = (len(s)-1)-i

相當於 i+j=len(s)-1。

len(s) 為 5,i 和 j 的相加為 4 ,因此需要減 1。


i 和 j 的其實還有另一層關係。

邏輯:
    由後往前看: -5  -4  -3  -2  -1
    由前往後看:  0   1   2   3   4
           s: ["h","e","l","l","o"]

頭和尾交換,i 是 0 的時候(由前往後看),j 是 -1(由後往前看),i 是 1 的時候,j 則是 -2。

簡單來說,這時候的 i 是前半部份往後看, j 是後半部份往前看。

因此,i +j = -1,也相當於 j+i=-1。

所以也可以寫成:

for i in range(len(s)//2):
    j + i=-1
    s[i], s[j] = s[j], s[i]

還有一種寫法,i 的值不由 j 決定,i 和 j 各走各的。

C 解答:

void reverseString(char* s, int sSize){               
   char* si = s;
        char* sj = s+sSize-1;
        while(si<sj){
            char t = *si;
            *si = *sj;
            *sj = t;
            si++;
            sj--;
        }   
}

Leave a Comment

Your email address will not be published. Required fields are marked *