您好,登錄后才能下訂單哦!
這篇文章主要講解了“C++怎么實(shí)現(xiàn)驗(yàn)證回文字符串”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“C++怎么實(shí)現(xiàn)驗(yàn)證回文字符串”吧!
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
驗(yàn)證回文字符串是比較常見的問題,所謂回文,就是一個正讀和反讀都一樣的字符串,比如“l(fā)evel”或者“noon”等等就是回文串。但是這里,加入了空格和非字母數(shù)字的字符,增加了些難度,但其實(shí)原理還是很簡單:只需要建立兩個指針,left和right, 分別從字符的開頭和結(jié)尾處開始遍歷整個字符串,如果遇到非字母數(shù)字的字符就跳過,繼續(xù)往下找,直到找到下一個字母數(shù)字或者結(jié)束遍歷,如果遇到大寫字母,就將其轉(zhuǎn)為小寫。等左右指針都找到字母數(shù)字時,比較這兩個字符,若相等,則繼續(xù)比較下面兩個分別找到的字母數(shù)字,若不相等,直接返回false.
時間復(fù)雜度為O(n), 代碼如下:
解法一:
class Solution { public: bool isPalindrome(string s) { int left = 0, right = s.size() - 1 ; while (left < right) { if (!isAlphaNum(s[left])) ++left; else if (!isAlphaNum(s[right])) --right; else if ((s[left] + 32 - "a") %32 != (s[right] + 32 - "a") % 32) return false; else { ++left; --right; } } return true; } bool isAlphaNum(char &ch) { if (ch >= "a" && ch <= "z") return true; if (ch >= "A" && ch <= "Z") return true; if (ch >= "0" && ch <= "9") return true; return false; } };
我們也可以用系統(tǒng)自帶的判斷是否是數(shù)母字符的判斷函數(shù)isalnum,參見代碼如下;
解法二:
class Solution { public: bool isPalindrome(string s) { int left = 0, right = s.size() - 1 ; while (left < right) { if (!isalnum(s[left])) ++left; else if (!isalnum(s[right])) --right; else if ((s[left] + 32 - "a") %32 != (s[right] + 32 - "a") % 32) return false; else { ++left; --right; } } return true; } };
感謝各位的閱讀,以上就是“C++怎么實(shí)現(xiàn)驗(yàn)證回文字符串”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對C++怎么實(shí)現(xiàn)驗(yàn)證回文字符串這一問題有了更深刻的體會,具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。