Coding interview練習 字串反轉

練習運用How to: Work at Google - Example Coding/Engineering interview 摘要的技巧處理字串反轉問題。

寫下問題

A:Build a function to reverse the given string.

e.g. 
  input:Hello
  output:olleH
  
  input:Show me the money
  output:yenom eht em wohS

提出問題

Q:字串的長度？
A:很長，超過一萬字的長度。

Q:字串會是空字串或是null嗎？
A:不會是null，可能會是空字串。

Q:有無記憶體限制？
A:假設沒有記體體限制。

Q:所以輸出的結果也是字串？
A:是，但必須是順序顛倒過來的。

先想到的解法

先想到的是直接用函式庫提供的方法。

Main.java

package com.abc.demo;

public class Main {

    public static void main(String[] arges) {
        System.out.println(reverse("Hello")); // olleH
        System.out.println(reverse("Show me the money")); // yenom eht em wohS
    }

    public static String reverse(String str) {
        return new StringBuilder(str).reverse().toString();
    }
}

當然不能用函式庫，所以直覺是建立另一個字元陣列，然後從原字串最後一個字開始依序塞到新的陣列。

Main.java

package com.abc.demo;

public class Main {

    public static void main(String[] arges) {
        System.out.println(reverse("Hello")); // olleH
        System.out.println(reverse("Show me the money")); // yenom eht em wohS
    }

    public static String reverse(String str) {
        char[] chars = new char[str.length()]; // 建立一個與輸入字串同長度的字元陣列 O(n)
        for (int i = str.length() - 1; i >= 0; i--) { // 遍歷字串，從最後開始走 O(n)
            chars[(str.length() - 1) - i] = str.charAt(i); // 放到新的字元陣列 O(1)
        }
        return new String(chars); // O(1)
    }
}

時間及空間複雜度

一個迴圈，大小為輸入字串的長度，時間複雜度為O(n)，為線性(linear)。

建立一個同輸入字串長度的陣列，空間複雜度為O(n)。

更加解

將字串前後對稱位置兩兩直接對調。

  ┌───────────────┐
  │   ┌───────┐   │
  ▼   ▼       ▼   ▼
┌───┬───┬───┬───┬───┐
│ H │ e │ l │ l │ o │
└───┴───┴───┴───┴───┘

不考慮str.toCharArray()函式內部複雜度的情況。建立一個暫存交換字元用的變數tmp時間O(1)，空間O(1)；使用輸入字串長度的一半跑回圈做頭尾字元交換為O(n/2)，不過計算複雜度去除乘數仍為O(n)。

Main.java

public class Main {

    public static void main(String[] arges) {
        System.out.println(reverse("Hello")); // olleH
        System.out.println(reverse("Show me the money")); // yenom eht em wohS
    }

    public static String reverse(String str) {
        char[] chars = str.toCharArray(); // 取得字串的字元陣列
        char tmp; // 建立一個字元變數用來作待會頭尾字元交換時的暫存空間
        for (int i = 0; i < chars.length/2; i++) { // 迴圈輸入字串的一半長度即可
            tmp = chars[i]; // 將第一個字元放到暫存變數
            chars[i] = chars[(chars.length - 1) - i]; // 將最後一個字元放到第一個索引
            chars[(chars.length - 1) - i] = tmp; // 將暫存變數的字元放到最後的索引。
        }
        return new String(chars); // 將字元陣列轉為字串
    }
}

• LeetCode Reverse String 字串反轉