題目 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer. Example:
Input: “cbbd”
Output: “bb” 思路 題目就就做最長的回文子串，題目沒有說清楚的是當(dāng)一個串的最長回文子串長度為1時，輸出串的第一個字符。 代碼思路解析： 用start，end來標(biāo)記每一次循環(huán)時一個子串的起始和終止索引，令i= start, j = end,然后逐個字符比較，符合回文條件的子串用一個字符串str保存起來并記錄最長的回文串，注意當(dāng)記錄的最長子串大于end-start+1時，直接退出當(dāng)前一層的循環(huán)(不加這個限制，程序會超時) 題目邊界條件注意 : 串s長度 < 2時 直接return s; 代碼
string find(string s){ if(s.size() < 2) return s; //串長度小于2，return s; int i,j,len,start,end; int maxLen = 1; len = s.size(); string str = s.substr(0,1); //若該串的最長回文串長度為1，返回第一個字符 for(start = 0; start < len - 1; start++){ //記錄子串的開始位置 for(end = len-1; end > start ; end--){ //記錄子串的結(jié)束位置 if(end-start+1 <= maxLen) break; //當(dāng)找到的子串maxLen >= 子串的長度時，直接break; i = start; j = end; while(s[i] == s[j] && i < j){ i++; j--; } if(i >= j && maxLen < end - start + 1){ //當(dāng)找到更長的子串時 maxLen = end - start + 1; //記錄最長子串的長度 str = s.substr(start,end-start+1); //記錄該回文子串 } } } return str;}新聞熱點(diǎn)
疑難解答
