下面是CN人才網(wǎng)小編為大家解答騰訊2016軟開實習(xí)生筆試題目,歡迎大家閱讀。
騰訊2016軟開實習(xí)生筆試題目
問題:求給定字符串s的回文(palindrome)子串中,長度最大的回文子串的長度。
回文(palindrome)是指從左往右讀和從右往左讀字符串,看到的字符串都是一樣的。比如“cabbeaf”,回文子串包括”c”“aba”“abba”等,最長的子串是“abba”,長度為4.
程序輸入:“cabbeaf”
程序輸出:
// C++ program to find the length of the longest palindrome
// for string "abeba" , longest palindrome is "abeba", thus 5;
// use recursion with memorization method
#include
#include
#include
using namespace std;
class Solution
// b/e is the begin/end index of the string s
// dp[i][j] is the biggest length of palindrome of s[i][j]
int palLength(string s, int b, int e, vector>&dp)
if (dp[b][e] != 0) return dp[b][e];
if (b > e ) return 0;
if (b == e) { dp[b][e] = 1; return 1; }
//if s[b]=s[e], then move b forward and e backward and do recursion
if (s[b] == s[e]){
dp[b][e] = palLength(s, b + 1, e - 1, dp) + 2;
//else move b forward or e backward and find the bigger one
else dp[b][e] = std::max(palLength(s, b + 1, e, dp), palLength(s, b, e - 1, dp));
return dp[b][e];
public:
int findPalindrome(string s){
int n = s.size();
vector> dp(n, vector(n, 0));
return palLength(s, 0, n - 1, dp);
// Driver program to test above function
int main()
string s("cabbeaf");
Solution solution;
cout << solution.findPalindrome(s);
這道題在leetcode上見過類似的題目,leetcode上是要求所有可能的劃分結(jié)果和最少的劃分次數(shù),而這里只用求劃分之后的回文子串最長的長度就可以了。
用遞歸方法的思路是從字符串兩頭開始找,對于當(dāng)前頭b和當(dāng)前尾e指定的字符串s[b…e],如果頭和尾字符一樣s[b]=s[e],那么最大回文子串長度就是s[b+1 … e-1]的最大回文子串長度加上2;如果頭和尾字符不一樣,那么頭和尾各移動一步求回文子串長度,即求s[b+1…e]和s[b…e-1]的回文子串長度,然后s[b…e]的最大回文子串長度就是s[b+1…e]和s[b…e-1]中的最大值。遞歸結(jié)束條件是b>=e,這里有一點注意的就是b>e,則返回0,b=e時按理說應(yīng)該返回1,因為對于一個字符,本身就可以看作是長度為1的回文。這里根據(jù)題目要求來做相應(yīng)判斷就可以了。
另外,為了避免遞歸做重復(fù)的工作,用一個矩陣dp來記錄已經(jīng)求得的部分的回文子串長度,初始dp矩陣的元素都為0,遞歸程序開始檢查dp[b][e]是不是為0,不為0則說明已經(jīng)找過了,直接返回該值就可以了。