切換
舊版
前往
大廳
主題

LeetCode - 125. Valid Palindrome 解題心得

Not In My Back Yard | 2020-08-24 00:00:13 | 巴幣 0 | 人氣 204

題目連結:


題目意譯:
給定一個字串 s,判斷其是否為一個迴文。只需考慮英文字母以及數字字元,其他字元以及大小寫的差異兩者皆忽略。

注:對於此題的要求,我們定義空字串是一個合法的迴文。

限制:
s 只由可印出的 ASCII 字元組成。



範例測資:
範例 1:
輸入: "A man, a plan, a canal: Panama"
輸出: true

範例 2:
輸入: "race a car"
輸出: false


解題思維:
可以先將所有不是英文或數字的字元全部挑掉,只留下要看的英文與數字。然後用一般判斷迴文的方式去判斷,如此題或是這題(不過這是純數字的)。



但是也可以只用兩個指標 L 、 R ,一個從頭掃、一個從尾掃。將 L 一直往尾端移動,略過中間非英數的字元直到碰到第一個英數字元,然後 R 也是如法炮製,只是換成往頭端方向移動。

L 、 R 兩指標皆定位之後,判斷兩者指到的字元是否相同,不同就一定不是迴文。相同就繼續比較下一個英數字元(跟前面的步驟一致),直到全部比完,此時才是迴文。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作