iT邦幫忙

2021 iThome 鐵人賽

DAY 9
1
Software Development

30天用JavaScript刷題刷起來!系列 第 9

Day 09: Valid Palindrome

相信迴文(palindrome)一定是在剛入門學習程式時一定會遇到的問題,
他雖然看起來很簡單,但的確可以教我們很多演算法上的思維。
本篇會提供三種解法,一起來看從暴力法到優雅的解題的過程吧!

迴文(palindrome)就是由前往後和由後往前念都像同的句子,像是'abcdcba'、'口罩罩口'...等等。


初學者一定有做過的方式,超直覺暴力法:

時間複雜度 : O(N^2) ,空間複雜度:O(N)

利用題目給你的字串反過來寫一次,也就是先建一個空字串,把字一個個加(concat)上去,這個步驟其實會造成O(N^2)的時間複雜度,而後我們又要把建立好的結果和原本的字串來做比對

程式碼會長得像下方⇊

function isPalindrome(string) {
  let reverseString = '';
  for (let i = string.length - 1; i >= 0; i--) {
    reverseString += string[i];
  }
  return string === reverseString;
}

當然我們不能在這裡就放過這一題,再想想有沒有更好的做法?

如果一開始我們不建立一個空字串,建立一個空的陣列,我們用push的方式把加到array 相較一開的方式,這樣只花O(N)

然後把新建的array.join()的方式變成字串和原本相比

function isPalindrome(string) {
  const reverseString = [];
  for (let i = string.length - 1; i >= 0; i--) {
    reverseString.push(string[i]);
  }
  return string === reverseString.join('');
}

那有沒有辦法用遞迴(Recursion)的方式解決呢?

利用 return first === last and isPalindrome(middle)

但是Recursion的方式不一定有辦法減少space

因為tail recursion依舊需要用到stack

程式碼如下

function isPalindrome(string, i = 0) {
  const j = string.length - 1 - i;
  return i >= j ? true : string[i] === string[j] && isPalindrome(string, i + 1);
}

那有沒有辦法減少空間複雜度?

當然可以!好用的pointer又派上用場了!

來看pointer的解法!

function isPalindrome(string) {
  let start = 0;
  let end = string.length - 1;
  while (start < end) {
    if (string[start] !== string[end]) return false;
    start++;
    end--;
  }
  return true;
}

看完這寫方式,Leetcode的題目指示加上一些變化,我們可以利用正則表達式

有關正則表達式,這裡提供最近保哥線上提供的最新影片直播連接fb,有需要的可以再去觀看!

下面提供解答參考拉!

var isPalindrome = function(s) {
  s = s.replace(/[^0-9a-zA-Z]+/gim, '');
  s = s.toLowerCase();
  let start = 0;
  let end = s.length - 1;
  while (start < end) {
    if (s[start] !== s[end]) return false;
    start++;
    end--;
  }
  return true;
};

明日題目預告:
摸過簡單的Palindrome,當然要來看進階一點的題目!Longest Palindromic Substring


上一篇
Day 08 : Longest Mountain in Array
下一篇
Day 10 :Longest Palindromic Substring
系列文
30天用JavaScript刷題刷起來!30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 則留言

1
TD
iT邦新手 4 級 ‧ 2021-09-25 09:20:27

這裡使用正則表達式是對應到題目的限制嗎?

s consists only of printable ASCII characters.

Jen iT邦新手 5 級 ‧ 2021-09-25 17:11:17 檢舉

是的!

str.replace(regexp|substr, newSubstr|function)

一二行可以直接寫成
s = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase()

0
Dylan
iT邦新手 3 級 ‧ 2021-11-08 17:39:45

不好意思,有點無法理解此 code 的時間複雜度為何是 O(n^2),我以為是 O(n)

function isPalindrome(string) {
  let reverseString = '';
  for (let i = string.length - 1; i >= 0; i--) {
    reverseString += string[i];
  }
  return string === reverseString;
}
Jen iT邦新手 5 級 ‧ 2021-11-09 00:45:39 檢舉

考慮最糟的情況下,原本的和反過來的比較後會發生。可以參考 https://stackoverflow.com/questions/24153433/complexity-of-palindrome-test

我要留言

立即登入留言