10钟前google电面

刚刚面完，目测已跪，发面经攒人品。
string题，第一问和leetcode上的shortest palindrome

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

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

帮助很大，以后有面经会继续回馈地里。
祝各位找工作顺利~走过路过打赏点米啊！

尝试了一下dp解法：dp[i][j]存从s[i]到s[j]的substring能够组成的最短palindrome

1. public static String shortestPalindrome2(String s) {
   
2.         if (s == null || s.length() <= 1) {
   
3.             return s;
   
4.         }
   
5.         String[][] dp = new String[s.length()][s.length()];
   
6.         for (int i = 0; i < s.length(); i++) {
   
7.             dp[i][i] = String.valueOf(s.charAt(i));
   
8.         }
   
9.         for (int len = 2; len <= s.length(); len++) {
   
10.             for (int i = 0; i <= s.length() - len; i++) {
    
11.                 if (s.charAt(i) == s.charAt(i + len - 1)) {
    
12.                     if (len == 2) {
    
13.                         dp[i][i + 1] = s.substring(i, i + 2);
    
14.                     } else {
    
15.                         dp[i][i + len - 1] = s.charAt(i) + dp[i + 1][i + len - 2] + s.charAt(i + len - 1);
    
16.                     }
    
17.                 } else {
    
18.                     if (len == 2) {
    
19.                         dp[i][i + 1] = s.substring(i, i + 2) + s.charAt(i);
    
20.                     } else {
    
21.                         dp[i][i + len - 1] = dp[i + 1][i + len - 1].length() < dp[i][i + len - 2].length() ?
    
22.                                 s.charAt(i) + dp[i + 1][i + len - 1] + s.charAt(i) : s.charAt(i + len - 1) + dp[i][i + len - 2] + s.charAt(i + len - 1);
    
23.                     }
    
24.                 }
    
25.             }
    
26.         }
    
27.         return dp[0][s.length() - 1];
    
28.     }

复制代码

string题，第一问和leetcode上的shortest palindrome 基本一样，换成了插在结尾，问题不大，讨论了下时间复杂度。
follow up问如果插字符在任何地方，看到过dp解法，但是想不起来也没推出来。搜了一下，类似 pku1159，
follow-up写了一下，大家看一下是否对了呢？
题意就是 求一个字符串最少用多少个字符使得整个字符串成为回文串。
Ab3bd,返回2

class Solution
{
public:
        int addChar(string str)
        {
                if(str.size() < 2)
                        return 0;

                string revStr(str.rbegin(), str.rend());

                return str.size() - LCS(str, revStr);
        }

        int LCS(string a, string b)
        {
                if(a.size() < 1 || b.size() < 1)
                        return 0;
                vector<int> pre(b.size()+1);

                for(int i = 1; i <= a.size(); i++)
                {
                        vector<int> cur(b.size()+1);
                        for(int j = 1; j <= b.size(); j++)
                        {
                                if(a[i-1] == b[j-1])
                                        cur[j] = pre[j-1] + 1;
                                else
                                        cur[j] = max(cur[j-1], pre[j]);
                        }
                        pre = cur;
                }
                return pre[b.size()];
        }
};


//int main()
//{
//        string str("AC");
//        Solution ss;
//        cout<<ss.addChar(str);
//        int i = 0;
//}

请问lz是用KMP算法么？感觉店面就考KMP算法好难。。。。

宝贝忆彼岸 发表于 2015-8-29 03:05
请问lz是用KMP算法么？感觉店面就考KMP算法好难。。。。

一开始写了暴力，问优化的时候写了KMP，因为刷过才记得，所以当时还觉得很走运。。。

laurie洁 发表于 2015-8-29 03:28
尝试了一下dp解法：dp[j]存从s到s[j]的substring能够组成的最短palindrome

谢谢！学习了！

这还不是叼难。 这难的题。 楼主是面哪个office?

zchang3 发表于 2015-8-29 03:46
一开始写了暴力，问优化的时候写了KMP，因为刷过才记得，所以当时还觉得很走运。。。

可以问问KMP怎么写吗？想学习一下~~

第二个题目 任何 位置应该可以dp接， geeksforgeeks有原题

laurie洁 发表于 2015-8-29 04:02
可以问问KMP怎么写吗？想学习一下~~

1. 
   
2. string solver(string a){
   
3.     string re=a;
   
4.     reverse(re.begin(),re.end());
   
5.     string t=re+"#"+a;
   
6.     vector<int> p(t.size(),0);
   
7.     for (int i = 1; i < t.size(); ++i) {
   
8.         int j = p[i - 1];
   
9.         while (j > 0 && t[i] != t[j])
   
10.             j = p[j - 1];
    
11.         j+=(t[i]==t[j]);
    
12.         p[i] = j;
    
13.     }
    
14.     for(int i=0;i<p.size();i++)
    
15.         cout<<p[i]<<' ';
    
16.     cout<<endl;
    
17.     return a.substr(0,a.size()-p[t.size() - 1]) + re;
    
18. }

复制代码

补充内容 (2015-8-29 05:17):
中间的cout忘删了...原题是在 https://leetcode.com/problems/shortest-palindrome/

hulahu 发表于 2015-8-29 03:55
这还不是叼难。 这难的题。 楼主是面哪个office?

小哥说google now，前几天看新闻说已经全体离职了？记不清了一开始挺紧张，杂音也大听不很清