Data Structure: Arrays Exercise - Reverse A String

Reverse A String: 把任意input的string倒敘排列

JavaScript:

解法一：先把input string轉換成array，組合後再轉回string，最後return

Time Complexity: O(n)

for loop會iterate整個string → O(n)

join會iterate整個array → O(n)

Space Complexity: O(n)

push把資料一個一個放入result array → O(1)

join會建立新的string，長度等於input string → O(n)

function reverseString(input) {
    // check input is string or string length less than 2
    // Time Complexity: O(1)
    if(!input || typeof input != 'string' || input.length < 2 ) {
        return input
    }

    // Space Complexity: O(n)
    const result = []
    const totalItems = input.length - 1
    // Time Complexity: O(n)
    for(let i = totalItems; i >= 0; i--){
        // Time Complexity: O(1)
        result.push(str[i])
    }

    // Time Complexity: O(n)
    // Space Complexity: O(n)
    return result.join('')
}

解法二：直接運用現有的Array methods

Time Complexity: O(n)

split會iterate整個string → O(n)

reverse和join會iterate整個array → 都是O(n)

Space Complexity: O(n)

split會建立新的array，長度等於input string → O(n)

reverse原地反轉整個array，不需建立新的array → O(1)

join會建立新的string，長度等於input string → O(n)

function reverseString(input) {
    return input.split('').reverse().join('')
}

解法三：直接運用現有的Array methods，搭配spread operator

Time Complexity: O(n)

[...input]會iterate整個string → O(n)

reverse和join會iterate整個array → 都是O(n)

Space Complexity: O(n)

[...input]會建立新的array，長度等於input string → O(n)

reverse原地反轉整個array，不需建立新的array → O(1)

join會建立新的string，長度等於input string → O(n)

// [...input]效果等同於split('')
const reverseString = input => [...input].reverse().join('')

Go:

解法一：直接從input string的最後開始iterate，把結果存到output string，最後回傳

Time Complexity: O(n)

for loop會iterate整個string → O(n)

Space Complexity: O(n)

建立新的變數output來儲存for loop iterate的結果 → O(n)

缺點：

方法一比較適合input string長度較短的情境，因為當input string很長的時候，每次執行for迴圈都會建立一個新的output，且在memory上，每建立一個新的output，就需要釋放舊的output，不斷建立和釋放會降低執行效能

func reverseString(input string) string {
    // check the input length
    if len(input) < 2 {
        return input
    }

    output := ""
    for i := len(input) - 1; i >= 0; i-- {
        output += string(input[i])
    }

    return output
}

方法二：建立rune slice，之後都只在這個slice上反轉rune的排序，最後把rune轉換成string再return，適合應用在有Unicode的情境

Time Complexity: O(n)

執行for loop → O(n)

string(output)iterate rune slice，轉換成string→ O(n)

Space Complexity: O(n)

output := []rune(input)建立與input string長度相當的rune slice → O(n)

func reverseString(input string) string {
    // check the input length
    if len(input) < 2 {
        return input
    }

    output := []rune(input)
    // i < j 確保了只有iterate到rune slice的中間，避免了不必要的交換操作
    for i, j := 0, len(output)-1; i < j; i, j = i+1, j-1 {
        // "同時"交換位置
        output[i], output[j] = output[j], output[i]
        // 錯誤寫法：
        // output[i] = output[j]
        // output[j] = output[i]
    }
    return string(output)
}

方法三：把使用情境細分成分別處理ASCII和Unicode，因為Unicode包含了ASCII，先判斷是ASCII，就能直接用效率較高的byte slice[]byte處理，Unicode則用rune slice[]rune處理，不論哪種處理方式，最後都會再轉換成string後回傳

Time Complexity: O(n)

for loop iterate input string逐一檢查是否為純ASCII → O(n)

不論是byte slice方法或rune slice方法，都會執行迴圈轉換位置 → O(n)

string(b)/string(r)iterate byte slice/ rune slice，轉換成string→ O(n)

Space Complexity: O(n)

b := []byte(input)建立與input string長度相當的byte slice → O(n)

r := []rune(input)建立與input string長度相當的rune slice → O(n)

func reverseString(input string) string {
    if len(input) < 2 {
        return input
    }

    // 檢查是否為純 ASCII
    isASCII := true
    for i := 0; i < len(input); i++ {
        // input[i]:
        // 是ASCII時，結果會是ASCII int
        // 非ASCII時，結果會是大於127的int
        if input[i] > 127 {
            isASCII = false
            break
        }
    }

    if isASCII {
        // 使用byte slice方法處理ASCII
        b := []byte(input)
        for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
            b[i], b[j] = b[j], b[i]
        }
        return string(b)
    } else {
        // 使用rune slice方法處理Unicode
        r := []rune(input)
        for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
            r[i], r[j] = r[j], r[i]
        }
        return string(r)
    }
}