最近去面試,考了一題簡單的白版題,題目為判斷傳入的字串是否為回文(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 則留言:
意外來到這裡~
除了整串字串 之前面試還有被問過 如果還要考慮裡面的substring 是否為Palindrome 要怎麼做~
算是滿好玩的
張貼留言