GOOGLE 二面面经

感觉不用DP呀  我这么写的 不知道对不对


def chunked(parlin):
    result = 0
    length = len(parlin)
    mid = (1+length)/2 -1
    tail , head = 0, 0
    while tail <= mid:
        if tail == mid:
            result += 1
            tail += 1
        else:
            if parlin[head:tail+1] == parlin[length-tail-1:length-head]:
                head= tail+1
                tail = tail +1
                result += 2
            else:
                tail += 1
    return result

请问楼主最后onsite了吗？

bobzhang2004 发表于 2016-3-31 12:06
请问楼主最后onsite了吗？

没有，跪了

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

如果是 odd string 最后的if（i＝＝j）可以合并到prev_i<=prev_j吧

see_you2012 发表于 2016-1-28 11:45
写了一个递归的，改成迭代的也不难，有问题请指出~
int countChunk(string input) {
        if (input.length( ...

我看了一圈, 就你这个对..结果你              
  return 2+ chunkNum(s.substring(i,s.length()-i)); <--这个为什么多个2*i

试着写了一下, 双指针, On 时间复杂度. 可能会有conner case, 但是上面大家例子,都可以通过.

   
    public static int chunkedPalindrome(String s) {
        int l = 0, r = s.length() -1;
        int count = 0;
        while (l <= r) {
            if (s.charAt(l) == s.charAt(r)) {
                if (l == r) count+=1;
                else count +=2;
                l++;
                r--;
            } else {
                int pl = l, pr = r;
                while (l < r && !s.substring(pl,l+1).equals(s.substring(r,pr+1))) {
                    l++;
                    r--;
                }
                if (l < r) count+=2;
                else count+=1;
                l++;r--;
            }
        }
        return count;
    }

mdyuki1016 发表于 2016-6-19 07:43
试着写了一下, 双指针, On 时间复杂度. 可能会有conner case, 但是上面大家例子,都可以通过.

   

嗯。。感觉这个是对的呢。。就是贪心的思路，尽可能的把前后的字符串匹配上。。这样就能产生最多的chunk。。