求问FB题目 - 未名空间MITBBS历史存档

L*12015-01-22 08:01

1 楼

FB面经里面的，没想明白怎么做，望各位大牛赐教。
1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB,考虑pattern是有序的。
就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
，得把leftBound前进到第2个X。
2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
续的几个数之和等于target number 要用O(n) time
感觉是DP，但是没什么头绪。
3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom
谢谢

t*o2015-01-22 08:01

2 楼

第2题可不可以这么做，首先用一个hashmap记录每一个位置i，从index 0 到 i所有数
字之和，从头到尾维护一个sum变量，然后在每一个index，检查sum－n是不是已经出现
过，假设在index j，前j个数和为k－n，在index i（i>j），前i个数的和为k，那么从
j+1到i的和就是n了。

P*i2015-01-22 08:01

3 楼

Hash cumsum
[在 teedoo (teedoo) 的大作中提到：]
：第2题可不可以这么做，首先用一个hashmap记录每一个位置i，从index 0 到 i所有数
：字之和，从头到尾维护一个sum变量，然后在每一个index，检查sum－n是不是已经出
现过，假设在index j，前j个数和为k－n，在index i（i>j），前i个数的和为k，
那么从j+1到i的和就是n了。
：...........

c*m2015-01-22 08:01

4 楼

写写自己的理解
1. DP
f(i,j)为母串s[0,...,i]匹配到子串p[0,...j]的最短substring的长度，则
f(i,j) = f(i-1,j-1)+1, if s[i]==p[j]
= f(i-1,j)+1, if s[i]!=p[j]
然后要用另外一个二维数组记录f(i,j)的前面是哪个操作，j-1或者j,i始终减1
最后查找f(i,n)哪个最小，n为子串的长度，并且回溯找到起始的index，返回值
2. 将(0,i)的和存在hashmap >，key为(0,i)的和，vector记
录具有相同和的下标。然后从头开始，对于i，如果(0,i)的和为sum, 找sum-x是否在
hashmap中，如果在且vector中有小于i的下标，存在，否则i++;
3. 能想到的就是建一个trie，然后brute force

【在 L*****1 的大作中提到】

: FB面经里面的，没想明白怎么做，望各位大牛赐教。
: 1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
: 底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
: ，得把leftBound前进到第2个X。
: 2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
: 续的几个数之和等于target number 要用O(n) time
: 感觉是DP，但是没什么头绪。
: 3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom

k*e2015-01-22 08:01

5 楼

2 .
Sum + hash

b*e2015-01-22 08:01

6 楼

1. 把无关的char忽视然后直接kmp。

【在 L*****1 的大作中提到】

: FB面经里面的，没想明白怎么做，望各位大牛赐教。
: 1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
: 底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
: ，得把leftBound前进到第2个X。
: 2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
: 续的几个数之和等于target number 要用O(n) time
: 感觉是DP，但是没什么头绪。
: 3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom

d*82015-01-22 08:01

7 楼

请问能具体解释一下在下面这个例子中KMP如何发挥作用么? 多谢.
S = "ABBCCD"
P = "ABCD"
如何忽略无关的char然后用KMP搜索啊? 按照我的理解,S中所有的char都是相关的char,
在S中是搜索不到"ABCD"这个子串的.

【在 b***e 的大作中提到】

: 1. 把无关的char忽视然后直接kmp。

z*b2015-01-22 08:01

8 楼

http://www.quora.com/Given-an-input-array-of-integers-of-size-n
第一题有比这个答案更好的吗？

s*z2015-01-22 08:01

9 楼

第三题是这样，每次碰到一个string，看其substring(0 - i) 是否是palindrome，如
果是，再看substring(i)的 reverse是否存在在hashmap中，如果是同时满足这两个条
件，存成一个pair结果。如果不满足，就直接存到hashmap里面。
以上操作做完有一个bug，就是只能看短的palindrome段出现的比长的早。所以要把全
部单词都reverse一下，再做一遍。然后再得到一堆pair。
以上所有pair里面维护一个最大长度的就行了

I*g2015-01-22 08:01

10 楼

第一题：
public static String shortestString(String s, String p){
String result = null;
if (s== null || p == null || p.length() >s.length()) return null;
if (s.length() ==0 || p.length() ==0) return "";
Map indexMap = new HashMap();
List indexList = new ArrayList();
int min = s.length() +1;

for(int i =0 ;i < s.length(); i++){
for(Integer x: indexList){
int j = indexMap.get(x);
if ( j < p.length()-1 &&(p.charAt(j+1) == s.charAt(i))){
indexMap.put(x, j+1);
if( j == p.length()-2 && i -x +1 < min){
min = i-x +1;
result = s.substring(x, i+1);
}
}
}
if (s.charAt(i) == p.charAt(0)){
indexList.add(i);
indexMap.put(i, 0);
}
}
return result;
}

【在 L*****1 的大作中提到】

: FB面经里面的，没想明白怎么做，望各位大牛赐教。
: 1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
: 底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
: ，得把leftBound前进到第2个X。
: 2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
: 续的几个数之和等于target number 要用O(n) time
: 感觉是DP，但是没什么头绪。
: 3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom

h*s2015-01-22 08:01

11 楼

好方法，应该也是 O(nk)吧？ k是pattern的长度，n是s的长度。
indexMap记录的是从index i开始能够最远match到p的index j+1。

【在 I*******g 的大作中提到】
: 第一题：
: public static String shortestString(String s, String p){
: String result = null;
: if (s== null || p == null || p.length() >s.length()) return null;
: if (s.length() ==0 || p.length() ==0) return "";
: Map indexMap = new HashMap();
: List indexList = new ArrayList();
: int min = s.length() +1;
:
: for(int i =0 ;i < s.length(); i++){

b*e2015-01-22 08:01

12 楼

KMP is not exactly accurate in this case. What I really mean is that
this is a standard regex matching problem, to its essence. For
instance, if you have a pattern XXA, then the regex would be
var p = /.*X.*X.*A.*/;
All you need to do is to figure out the deterministic finite state
automata (DFSA) corresponding to this regex and apply it on S. The
construction of the DFA is bound to O(2^k) where k is the length of P.
But after that the matching would be O(n) where n is the length of S.
So the time complexity for this is O(min(n, 2^k)). Practically, k is
small, and the naive construction of the DFSA does not take as high as
2^k.

char,

【在 d*******8 的大作中提到】

: 请问能具体解释一下在下面这个例子中KMP如何发挥作用么? 多谢.
: S = "ABBCCD"
: P = "ABCD"
: 如何忽略无关的char然后用KMP搜索啊? 按照我的理解,S中所有的char都是相关的char,
: 在S中是搜索不到"ABCD"这个子串的.

t*r2015-01-22 08:01

13 楼

这是电面题么？

t*a2015-01-22 08:01

14 楼

这个解法不对啊。
首先，一个单词substring(0 - i) 可能不是palindrome, 但和另一个单词合在一起是
palindrome。比如adcb, bcda.
其次，题目是可以组合任意个单词，不止两个。也许所有字典里的单词合在
一起是一个palindrome.

【在 s*******z 的大作中提到】

: 第三题是这样，每次碰到一个string，看其substring(0 - i) 是否是palindrome，如
: 果是，再看substring(i)的 reverse是否存在在hashmap中，如果是同时满足这两个条
: 件，存成一个pair结果。如果不满足，就直接存到hashmap里面。
: 以上操作做完有一个bug，就是只能看短的palindrome段出现的比长的早。所以要把全
: 部单词都reverse一下，再做一遍。然后再得到一堆pair。
: 以上所有pair里面维护一个最大长度的就行了

y*e2015-01-22 08:01

15 楼

第一题好难。。

z*b2015-01-22 08:01

16 楼

你能把这个代码的思想说的详细点吗？谢谢！

【在 I*******g 的大作中提到】

: 第一题：
: public static String shortestString(String s, String p){
: String result = null;
: if (s== null || p == null || p.length() >s.length()) return null;
: if (s.length() ==0 || p.length() ==0) return "";
: Map indexMap = new HashMap();
: List indexList = new ArrayList();
: int min = s.length() +1;
:
: for(int i =0 ;i < s.length(); i++){

R*G2015-01-22 08:01

17 楼

3 －任意个单词怎么做啊？

【在 L*****1 的大作中提到】

: FB面经里面的，没想明白怎么做，望各位大牛赐教。
: 1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
: 底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
: ，得把leftBound前进到第2个X。
: 2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
: 续的几个数之和等于target number 要用O(n) time
: 感觉是DP，但是没什么头绪。
: 3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom

G*m2015-01-22 08:01

18 楼

第三题怎么解？
谢谢！

【在 L*****1 的大作中提到】

: FB面经里面的，没想明白怎么做，望各位大牛赐教。
: 1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
: 底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
: ，得把leftBound前进到第2个X。
: 2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
: 续的几个数之和等于target number 要用O(n) time
: 感觉是DP，但是没什么头绪。
: 3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom

w*d2015-01-22 08:01

19 楼

3题，是否还有限制每个单词只能用一次？否则，如果字典里有一个回文单词w，那么无
限个w连接起来还是回文。
不过即使加这个限制，这个题貌似也没有多项式时间的解法。

b*h2015-01-22 08:01

20 楼

你这个最坏情况会达到n^2，比如在ABABABA....ABABC中找ABC
其实只需要记录每个prefix最近一次出现的index，不需要把每个prefix所有出现的都
存下来，这样可以O(nk)

【在 I*******g 的大作中提到】

: 第一题：
: public static String shortestString(String s, String p){
: String result = null;
: if (s== null || p == null || p.length() >s.length()) return null;
: if (s.length() ==0 || p.length() ==0) return "";
: Map indexMap = new HashMap();
: List indexList = new ArrayList();
: int min = s.length() +1;
:
: for(int i =0 ;i < s.length(); i++){

L*12015-01-22 08:01

21 楼

FB面经里面的，没想明白怎么做，望各位大牛赐教。
1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB,考虑pattern是有序的。
就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
，得把leftBound前进到第2个X。
2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
续的几个数之和等于target number 要用O(n) time
感觉是DP，但是没什么头绪。
3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom
谢谢

t*o2015-01-22 08:01

22 楼

第2题可不可以这么做，首先用一个hashmap记录每一个位置i，从index 0 到 i所有数
字之和，从头到尾维护一个sum变量，然后在每一个index，检查sum－n是不是已经出现
过，假设在index j，前j个数和为k－n，在index i（i>j），前i个数的和为k，那么从
j+1到i的和就是n了。

P*i2015-01-22 08:01

23 楼

Hash cumsum
[在 teedoo (teedoo) 的大作中提到：]
：第2题可不可以这么做，首先用一个hashmap记录每一个位置i，从index 0 到 i所有数
：字之和，从头到尾维护一个sum变量，然后在每一个index，检查sum－n是不是已经出
现过，假设在index j，前j个数和为k－n，在index i（i>j），前i个数的和为k，
那么从j+1到i的和就是n了。
：...........

c*m2015-01-22 08:01

24 楼

写写自己的理解
1. DP
f(i,j)为母串s[0,...,i]匹配到子串p[0,...j]的最短substring的长度，则
f(i,j) = f(i-1,j-1)+1, if s[i]==p[j]
= f(i-1,j)+1, if s[i]!=p[j]
然后要用另外一个二维数组记录f(i,j)的前面是哪个操作，j-1或者j,i始终减1
最后查找f(i,n)哪个最小，n为子串的长度，并且回溯找到起始的index，返回值
2. 将(0,i)的和存在hashmap >，key为(0,i)的和，vector记
录具有相同和的下标。然后从头开始，对于i，如果(0,i)的和为sum, 找sum-x是否在
hashmap中，如果在且vector中有小于i的下标，存在，否则i++;
3. 能想到的就是建一个trie，然后brute force

【在 L*****1 的大作中提到】

: FB面经里面的，没想明白怎么做，望各位大牛赐教。
: 1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
: 底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
: ，得把leftBound前进到第2个X。
: 2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
: 续的几个数之和等于target number 要用O(n) time
: 感觉是DP，但是没什么头绪。
: 3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom

k*e2015-01-22 08:01

25 楼

2 .
Sum + hash

b*e2015-01-22 08:01

26 楼

1. 把无关的char忽视然后直接kmp。

【在 L*****1 的大作中提到】

: FB面经里面的，没想明白怎么做，望各位大牛赐教。
: 1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
: 底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
: ，得把leftBound前进到第2个X。
: 2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
: 续的几个数之和等于target number 要用O(n) time
: 感觉是DP，但是没什么头绪。
: 3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom

d*82015-01-22 08:01

27 楼

请问能具体解释一下在下面这个例子中KMP如何发挥作用么? 多谢.
S = "ABBCCD"
P = "ABCD"
如何忽略无关的char然后用KMP搜索啊? 按照我的理解,S中所有的char都是相关的char,
在S中是搜索不到"ABCD"这个子串的.

【在 b***e 的大作中提到】

: 1. 把无关的char忽视然后直接kmp。

z*b2015-01-22 08:01

28 楼

http://www.quora.com/Given-an-input-array-of-integers-of-size-n
第一题有比这个答案更好的吗？

s*z2015-01-22 08:01

29 楼

第三题是这样，每次碰到一个string，看其substring(0 - i) 是否是palindrome，如
果是，再看substring(i)的 reverse是否存在在hashmap中，如果是同时满足这两个条
件，存成一个pair结果。如果不满足，就直接存到hashmap里面。
以上操作做完有一个bug，就是只能看短的palindrome段出现的比长的早。所以要把全
部单词都reverse一下，再做一遍。然后再得到一堆pair。
以上所有pair里面维护一个最大长度的就行了

I*g2015-01-22 08:01

30 楼

第一题：
public static String shortestString(String s, String p){
String result = null;
if (s== null || p == null || p.length() >s.length()) return null;
if (s.length() ==0 || p.length() ==0) return "";
Map indexMap = new HashMap();
List indexList = new ArrayList();
int min = s.length() +1;

for(int i =0 ;i < s.length(); i++){
for(Integer x: indexList){
int j = indexMap.get(x);
if ( j < p.length()-1 &&(p.charAt(j+1) == s.charAt(i))){
indexMap.put(x, j+1);
if( j == p.length()-2 && i -x +1 < min){
min = i-x +1;
result = s.substring(x, i+1);
}
}
}
if (s.charAt(i) == p.charAt(0)){
indexList.add(i);
indexMap.put(i, 0);
}
}
return result;
}

【在 L*****1 的大作中提到】

: FB面经里面的，没想明白怎么做，望各位大牛赐教。
: 1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
: 底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
: ，得把leftBound前进到第2个X。
: 2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
: 续的几个数之和等于target number 要用O(n) time
: 感觉是DP，但是没什么头绪。
: 3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom

h*s2015-01-22 08:01

31 楼

好方法，应该也是 O(nk)吧？ k是pattern的长度，n是s的长度。
indexMap记录的是从index i开始能够最远match到p的index j+1。

【在 I*******g 的大作中提到】
: 第一题：
: public static String shortestString(String s, String p){
: String result = null;
: if (s== null || p == null || p.length() >s.length()) return null;
: if (s.length() ==0 || p.length() ==0) return "";
: Map indexMap = new HashMap();
: List indexList = new ArrayList();
: int min = s.length() +1;
:
: for(int i =0 ;i < s.length(); i++){

b*e2015-01-22 08:01

32 楼

KMP is not exactly accurate in this case. What I really mean is that
this is a standard regex matching problem, to its essence. For
instance, if you have a pattern XXA, then the regex would be
var p = /.*X.*X.*A.*/;
All you need to do is to figure out the deterministic finite state
automata (DFSA) corresponding to this regex and apply it on S. The
construction of the DFA is bound to O(2^k) where k is the length of P.
But after that the matching would be O(n) where n is the length of S.
So the time complexity for this is O(min(n, 2^k)). Practically, k is
small, and the naive construction of the DFSA does not take as high as
2^k.

char,

【在 d*******8 的大作中提到】

: 请问能具体解释一下在下面这个例子中KMP如何发挥作用么? 多谢.
: S = "ABBCCD"
: P = "ABCD"
: 如何忽略无关的char然后用KMP搜索啊? 按照我的理解,S中所有的char都是相关的char,
: 在S中是搜索不到"ABCD"这个子串的.

t*r2015-01-22 08:01

33 楼

这是电面题么？

t*a2015-01-22 08:01

34 楼

这个解法不对啊。
首先，一个单词substring(0 - i) 可能不是palindrome, 但和另一个单词合在一起是
palindrome。比如adcb, bcda.
其次，题目是可以组合任意个单词，不止两个。也许所有字典里的单词合在
一起是一个palindrome.

【在 s*******z 的大作中提到】

: 第三题是这样，每次碰到一个string，看其substring(0 - i) 是否是palindrome，如
: 果是，再看substring(i)的 reverse是否存在在hashmap中，如果是同时满足这两个条
: 件，存成一个pair结果。如果不满足，就直接存到hashmap里面。
: 以上操作做完有一个bug，就是只能看短的palindrome段出现的比长的早。所以要把全
: 部单词都reverse一下，再做一遍。然后再得到一堆pair。
: 以上所有pair里面维护一个最大长度的就行了

y*e2015-01-22 08:01

35 楼

第一题好难。。

z*b2015-01-22 08:01

36 楼

你能把这个代码的思想说的详细点吗？谢谢！

【在 I*******g 的大作中提到】

: 第一题：
: public static String shortestString(String s, String p){
: String result = null;
: if (s== null || p == null || p.length() >s.length()) return null;
: if (s.length() ==0 || p.length() ==0) return "";
: Map indexMap = new HashMap();
: List indexList = new ArrayList();
: int min = s.length() +1;
:
: for(int i =0 ;i < s.length(); i++){

R*G2015-01-22 08:01

37 楼

3 －任意个单词怎么做啊？

【在 L*****1 的大作中提到】

: FB面经里面的，没想明白怎么做，望各位大牛赐教。
: 1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
: 底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
: ，得把leftBound前进到第2个X。
: 2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
: 续的几个数之和等于target number 要用O(n) time
: 感觉是DP，但是没什么头绪。
: 3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom

G*m2015-01-22 08:01

38 楼

第三题怎么解？
谢谢！

【在 L*****1 的大作中提到】

: FB面经里面的，没想明白怎么做，望各位大牛赐教。
: 1，给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
: 底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
: ，得把leftBound前进到第2个X。
: 2，给一个int array，有正有负，给一个target number，找出这个array里有没有连
: 续的几个数之和等于target number 要用O(n) time
: 感觉是DP，但是没什么头绪。
: 3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom

w*d2015-01-22 08:01

39 楼

3题，是否还有限制每个单词只能用一次？否则，如果字典里有一个回文单词w，那么无
限个w连接起来还是回文。
不过即使加这个限制，这个题貌似也没有多项式时间的解法。

b*h2015-01-22 08:01

40 楼

你这个最坏情况会达到n^2，比如在ABABABA....ABABC中找ABC
其实只需要记录每个prefix最近一次出现的index，不需要把每个prefix所有出现的都
存下来，这样可以O(nk)

【在 I*******g 的大作中提到】

: 第一题：
: public static String shortestString(String s, String p){
: String result = null;
: if (s== null || p == null || p.length() >s.length()) return null;
: if (s.length() ==0 || p.length() ==0) return "";
: Map indexMap = new HashMap();
: List indexList = new ArrayList();
: int min = s.length() +1;
:
: for(int i =0 ;i < s.length(); i++){

g*y2015-01-22 08:01

41 楼

貌似第一题的DP不work呀。

【在 c*****m 的大作中提到】

: 写写自己的理解
: 1. DP
: f(i,j)为母串s[0,...,i]匹配到子串p[0,...j]的最短substring的长度，则
: f(i,j) = f(i-1,j-1)+1, if s[i]==p[j]
: = f(i-1,j)+1, if s[i]!=p[j]
: 然后要用另外一个二维数组记录f(i,j)的前面是哪个操作，j-1或者j,i始终减1
: 最后查找f(i,n)哪个最小，n为子串的长度，并且回溯找到起始的index，返回值
: 2. 将(0,i)的和存在hashmap >，key为(0,i)的和，vector记
: 录具有相同和的下标。然后从头开始，对于i，如果(0,i)的和为sum, 找sum-x是否在
: hashmap中，如果在且vector中有小于i的下标，存在，否则i++;

p*g2015-01-22 08:01

42 楼

第一题感觉结合bunnih 的建议，稍微修改一下IFloating的算法来的简单。而且效果还
不错。基本和下面链接差不多的效果。
http://www.quora.com/Given-an-input-array-of-integers-of-size-n

【在 g*****y 的大作中提到】

: 貌似第一题的DP不work呀。

y*r2015-01-22 08:01

43 楼

试着写了一下，不知道对不对，求轻拍
public static String findMinimalWindow(String s, String t){
if(s==null || t==null || s.length()return null;
}
if(t.length()==0){
return "";
}
char[] cs=s.toCharArray();
char[] ct=t.toCharArray();
int n=cs.length, k=ct.length;
int[] lastDp=new int[n+1];
int[] dp = new int[n+1];
for(int j=0; jfor(int i=0; iif(cs[i] == ct[j]){
if(j==0){
dp[i+1]=i;
}else{
dp[i+1]=lastDp[i];
}
}else{
dp[i+1]=dp[i];
}
}
lastDp=dp;
dp = new int[n+1];
}
int min=Integer.MAX_VALUE;
String minStr = null;
for(int i=1; iif(lastDp[i] != 0 && (i-lastDp[i])min=i-lastDp[i];
minStr=s.substring(lastDp[i], i);
}
}
return minStr;
}

p*g2015-01-22 08:01

44 楼

不错。看明白了。
我也贴一下，求各位大牛给给意见。如果没问题, credits归IFloating和bunnih。
public static String shortestString(String s, String p){
String result = null;
if (s== null || p == null || p.length() >s.length()) return null;
if (s.length() ==0 || p.length() ==0) return "";
Map indexMap = new HashMap();
int min = s.length() +1;
for(int i =0 ;i < s.length(); i++){
for(Entry ent: indexMap.entrySet()){
int x = ent.getValue();
int j = ent.getKey();
if ( j < p.length()-1 &&(p.charAt(j+1) == s.charAt(i))){
indexMap.put(j+1,x);
if( j == p.length()-2 && i -x +1 < min){
min = i-x +1;
result = s.substring(x, i+1);
}
}
}

if (s.charAt(i) == p.charAt(0)){
indexMap.put(0, i);
}
}
return result;
}

【在 y***r 的大作中提到】

: 试着写了一下，不知道对不对，求轻拍
: public static String findMinimalWindow(String s, String t){
: if(s==null || t==null || s.length(): return null;
: }
: if(t.length()==0){
: return "";
: }
: char[] cs=s.toCharArray();
: char[] ct=t.toCharArray();