題目連結:
題目意譯:
給定一個字串 s,判斷其是否為一個迴文。只需考慮英文字母以及數字字元,其他字元以及大小寫的差異兩者皆忽略。
注:對於此題的要求,我們定義空字串是一個合法的迴文。
限制:
s 只由可印出的 ASCII 字元組成。
範例測資:
範例 1:
輸入: "A man, a plan, a canal: Panama"
輸出: true
範例 2:
輸入: "race a car"
輸出: false
解題思維:
可以先將所有不是英文或數字的字元全部挑掉,只留下要看的英文與數字。然後用一般判斷迴文的方式去判斷,如
此題或是
這題(不過這是純數字的)。
但是也可以只用兩個指標 L 、 R ,一個從頭掃、一個從尾掃。將 L 一直往尾端移動,略過中間非英數的字元直到碰到第一個英數字元,然後 R 也是如法炮製,只是換成往頭端方向移動。
L 、 R 兩指標皆定位之後,判斷兩者指到的字元是否相同,不同就一定不是迴文。相同就繼續比較下一個英數字元(跟前面的步驟一致),直到全部比完,此時才是迴文。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。