網頁

2019/10/9

Java Palindrome String

最近去面試,考了一題簡單的白版題,題目為判斷傳入的字串是否為回文(Palindrome String)。

所謂的Palindrome String(回文)是指字串不論正著念倒著念都是相同的,例如下面的字串皆為Palindrome String。

121
12233221
12121
9912840482199
aka
abba

題目要求寫一個方法判斷傳入的字串是否為Palindrome String。這題其實用迴圈(loop)就可以解了,但我當時緊張腦袋空白用了遞迴(recursion)解。

迴圈(loop)解

boolean isPalindrome(String s) {
    if (s == null) {
        return false;
    }

    char[] c = s.toCharArray();

    while (c.length > 0) {
        if (c.length == 1) { // 只剩一個字沒得比了,回傳true
            return true;
        }
        if (c[0] != c[c.length - 1]) { // 頭尾不同,回傳false
            return false;
        } else {
            c = Arrays.copyOfRange(c, 1,c.length-1); // 去除陣列的頭尾繼續比
            continue;
        }
    }
    return true; // 跳出迴圈代表已經沒字可比了,回傳true

}

遞迴(recursion)解。

boolean isPalindrome(String s) {
    if (s == null) {
        return false;
    }

    char[] c = s.toCharArray();

    if (c.length <= 1) { // 長度小於等於1,沒得比了,回傳true
        return true;
    }
    if (c[0] != c[c.length-1]) { // 頭尾不同,回傳false
        return false;
    }

    return isPalindrome(new String(Arrays.copyOfRange(c,1,c.length-1))); // recursion,除去陣列的頭尾繼續比
   
}

做法很簡單,就是比較頭尾字是否一樣,如果不一樣返回false,如果一樣就去頭去尾然後繼續往下比直到結束,最後只剩下一個字或沒剩下任何字返回true。但問題是輸入太長會導致OutOfMemoryError

1 則留言:

  1. 意外來到這裡~
    除了整串字串 之前面試還有被問過 如果還要考慮裡面的substring 是否為Palindrome 要怎麼做~
    算是滿好玩的

    回覆刪除