GOOGLE 二面面经

写了一个时间复杂度O(n^2)的
int countMaxChunks(string str) {
  int count = 0;
  int i = 0, j = str.size()-1; // scan from the two sides
  int prev_i = i, prev_j = j;
  while(i<j) {
    string chunk1 = str.substr(prev_i, i+1);
    string chunk2 = str.substr(j, prev_j+1);
    if (chunk1==chunk2) {
      count++;
      prev_i = i+1;
      prev_j = j-1;
    }   
    i++;
    j--;
  }
  count *= 2;
  // if odd string
  if (i==j)
    count++;
  // even string and still has chunk left
  else if (prev_i<prev_j)
    count++;
  return count;
}

补充内容 (2015-11-24 01:37):
思想比较简单，但是从string的两边开始，用i和j记录当前scan到的位置，用prev_i和prev_j记录上一次找到chunk的i和j的位置的下一个字符。最后扫到中间判断一下有无多余的chunk。

补充内容 (2015-11-24 01:38):
上面提到的测试都过了

lyudison 发表于 2015-11-24 01:34
写了一个时间复杂度O(n^2)的
int countMaxChunks(string str) {
  int count = 0;

我当时也是这思路写的，最后面试官说it should work

momo__ 发表于 2015-11-24 01:39
我当时也是这思路写的，最后面试官说it should work

意思是太渣了吗

lyudison 发表于 2015-11-24 02:07
意思是太渣了吗

不知道，还没收到HR的回复

lyudison 发表于 2015-11-24 01:34
写了一个时间复杂度O(n^2)的
int countMaxChunks(string str) {
  int count = 0;

为啥复杂度是O(n^2). 我觉得是O(n)

GatorAM 发表于 2015-11-24 05:33
为啥复杂度是O(n^2). 我觉得是O(n)

while一层循环，string比较是否相等又是一层。

lyudison 发表于 2015-11-24 09:48
while一层循环，string比较是否相等又是一层。

哦，酱紫

请问面试官有给hint吗?他期望的时间复杂度是多少呢？

楼主我也有几个问题。
1。输入一定是palindrome吗？abcbad 这总输入是不是不考虑
2.  输出是最大的chunk数量，对于  ababcabab, 返回一定是5 = (ab)(ab)c(ab)(ab) 还是 = (abab)c(abab)呢
谢谢！

补充内容 (2015-12-13 23:57):
3 =  = (abab)c(abab)

peter_jun 发表于 2015-12-13 23:56
楼主我也有几个问题。
1。输入一定是palindrome吗？abcbad 这总输入是不是不考虑
2.  输出是最大的chunk ...

你好， abcbad的话只能把它本身划分为一个大的chunk，所以chunk数量就是1.
ababcabab的话就是返回5.