脸家面筋

Josh 发表于 2016-9-12 08:22
a a b b c b a a a.
a: 0, 1, 6, 7, 8
b: 2, 3, 5

你的解法逻辑应该是对的，问下你这种解法和minimum window substring有很大区别吗？我感觉复杂度应该一样？

iPhD 发表于 2016-9-12 09:09
你的解法逻辑应该是对的，问下你这种解法和minimum window substring有很大区别吗？我感觉复杂度应该一样 ...

复杂度确实是一样的，应该区别不大吧，这个可能好跟面试官解释一点吧。可以说因为lo后面肯定会少一个char，hi前面肯定也少了一个char，所以lo不能往后移了hi也不能往前移了

Josh 发表于 2016-9-12 09:46
复杂度确实是一样的，应该区别不大吧，这个可能好跟面试官解释一点吧。可以说因为lo后面肯定会少一个char ...

这个做法怎么保证一定是最短的呢？
比如例子abcaabb:
第一遍
a: 0,3,4
b: 1,5,6
c: 2
按你的算法那lo＝2，扔掉了前面的ab
第二遍找caabb，结果是找到caab
但是最短的是abc啊？

daddev 发表于 2016-9-10 23:36
双指针实现O(n):  左指针初始指向位置0，右指针from 1 to len(str), 左右指针所指字符相同则左指针右移，因 ...

1 左右指针指向相同字符的时候可能需要移动不止一位
2 就算找到包含所有字符的子串还要继续查询， 因为最先找到的不一定最优

Josh 发表于 2016-9-10 12:15
先找出每个char最后一次出现的index，然后lo = 第一个最后出现的index
再找出每个char第一次出现的index， ...

如果字符串是 ”abcabbbc"
那么 lo 是最后一个 a，hi 是最后的 c，得到 abbbc，但是结果应该是 abc 吧？

kimiwang 发表于 2016-9-12 13:28
这个做法怎么保证一定是最短的呢？
比如例子abcaabb:
第一遍

多谢指正，看来这个做法有问题。那应该还是leetcode的写法吧

ofdk88 发表于 2016-9-12 15:23
请问楼主是网投还是内推？

内推的……

iPhD 发表于 2016-9-12 08:09
我觉得就是先扫一遍input string，取出所有distinct的字符组成一个target string，然后在原字符input str ...

嗯嗯，我觉得是这样