facebook 电面

一道很简单的题，结果自己脑抽，绕进去了

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

abba' 返回6

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这个题我以前自己做过，不过只有O(n^2)的方法，不过代码很少，想法也比较直接。：check所有的连续substring 是否是palindrome ,  存进hashmap，最后输出map的key的数量。
代码就不贴了。

谢楼主分享，继续加油了！

这是lc原题。一个月前我面f全职遇到的也是lc原题，做出来了，但是面试官让我优化，我不会，所以fail。他家的面试题lc里的不少。

rengokantai 发表于 2014-10-30 00:25
这是lc原题。一个月前我面f全职遇到的也是lc原题，做出来了，但是面试官让我优化，我不会，所以fail。他家 ...

跟leetcode还是不一样的

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

恩，感觉和ON回文方法类似，这题应该还是ON的最优解吧，只是判重的话多个hashtable罢了

我一开始理解错题目了，居然YY成跟子序列差不多的那种情况，感觉好复杂。。原题还是挺好写的，贴一下我的c++代码，大家看看有没有bug。

1. #include <iostream>
   
2. #include <string>
   
3. using namespace std;
   
4. 
   
5. const int MAX = 1002;
   
6. 
   
7. int dp[MAX][MAX];
   
8. 
   
9. void solve(string &s){
   
10.     int len = s.length();
    
11.     for(int i=0;i<len;++i){
    
12.         for(int j=0;j<len;++j){
    
13.             dp[i][j] = i>=j?1:0;
    
14.         }
    
15.     }
    
16.     int res = len;
    
17.     for(int k=2;k<=len;++k){
    
18.         for(int i=0;i<len;++i){
    
19.             int j = i+k-1;
    
20.             if(j>=len)  break;
    
21.             if(s[i] == s[j] && dp[i+1][j-1] == 1){
    
22.                 dp[i][j] = 1;
    
23.                 ++res;
    
24.             }
    
25.             
    
26.         }
    
27.     }
    
28.     printf("%d\n", res);
    
29. }
    
30. 
    
31. int main(){
    
32.     string s;
    
33.     while(cin>>s){
    
34.         solve(s);
    
35.     }
    
36. }
    

复制代码