描述
判斷一個(gè)由字母软能、數(shù)字和空格組成的字符串是否是回文舔示。
約束：
? 空字符串為回文；
示例：
? ”A man, a plan, a canal: Panama”是回文
”race a car” 非回文。
分析
采用兩端遍歷的方法，分別從左向右捂掰，從右向左進(jìn)行遍歷。
1）左索引為非字母曾沈、非數(shù)字則向右移動(dòng)一個(gè)位置这嚣；
2）右索引為非字母、非數(shù)字則向左移動(dòng)一個(gè)位置塞俱；
3）左右索引的值不相等姐帚，判斷為非回文；
4）左索引大于等于右索引則字符串為回文障涯，結(jié)束循環(huán)罐旗；
實(shí)現(xiàn)
bool isPalindrome(string s)
{
transform(s.begin(), s.end(), s.begin(), ::tolower);
auto left = s.begin();
auto right = prev(s.end());
while (left < right) {
if (!::isalnum(*left)) {
++left;
}
else if (!::isalnum(*right)) {
--right;
}
else if(*left != *right) {
return false;
}
++left;
--right;
}
return true;
}
時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)像樊。
