这个题目难度在leetcode里算什么 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

这个题目难度在leetcode里算什么

这个题目难度在leetcode里算什么# JobHunting - 待字闺中

I*g2015-01-23 08:01

1 楼

如果onsite你能几分钟写出来bug free 的code？
You are given a string, S, and a list of words, L, that are all of the same
length. Find all starting indices of substring(s) in S that is a
concatenation of each word in L exactly once and without any intervening
characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].

y*k2015-01-23 08:01

2 楼

中上吧.
不算太难

I*g2015-01-23 08:01

3 楼

你贴一个code

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

: 中上吧.
: 不算太难

r*e2015-01-23 08:01

4 楼

这个写起来挺头疼的。

k*a2015-01-23 08:01

5 楼

这个要写好很难

c*m2015-01-23 08:01

6 楼

之前写过一次，错了无数次才对。后来看了别人的优化code，今天再写一次，还是漏了
母串子串比较长度的corner case.
class Solution {
public:
vector findSubstring(string S, vector &L) {
vector result;
if (L.size() == 0) {
return result;
}
map expected;
for (int i = 0; i < L.size(); i++) {
expected[L[i]]++;
}
int wordLen = L[0].length();
//length compare
if (wordLen > S.length()) {
return result;
}
for (int i = 0; i < wordLen; i++) {
//offset: 0,1,2
int l = i;
int h = i;
int cnt = 0;
map real;
while (l <= S.length()-wordLen && h <= S.length()-wordLen ) {
string word = S.substr(h, wordLen);
if (real[word] < expected[word]) {
real[word]++;
cnt++;
if (cnt == L.size()) {
//get enough words
result.push_back(l);
}
h+=wordLen;
} else {
word = S.substr(l, wordLen);
real[word]--;
cnt--;
l+=wordLen;
}
}
}
return result;
}
};
//1. L[0].length() < S.length()

y*k2015-01-23 08:01

7 楼

我assume了L里面是没有duplicate的.如果要考虑有duplicate的话,把set换成hashmap.
public class Solution {
public static void main(String[] args) {
String S = "barfoothefoobarman";
List L = new LinkedList();
L.add("foo");
L.add("bar");
search(S, L);
}

public static List search(String S, List L) {
List result = new LinkedList<>();
int len = L.get(0).length();
HashSet set = new HashSet<>(L);
for (int offset = 0; offsetsearchInTokens(tokenize(S,offset,len), set, offset, len, result);
}
return result;
}

private static void searchInTokens(List tokens, HashSet
set, int offset, int len, List result) {
int start = 0, end = 0;
HashSet notFound = new HashSet(set);
while (end < tokens.size()) {
String s = tokens.get(end);
if (notFound.contains(s)) {
end++;
notFound.remove(s);
if (notFound.isEmpty()) {
System.out.println(offset+start*len);
result.add(offset + start*len);
notFound.add(tokens.get(start++));
}
}
else if (!set.contains(s)) {
if (notFound.size() != set.size())
notFound = new HashSet(set);
end++;
start = end;
}
else {
while (!s.equals(tokens.get(start))) {
notFound.add(tokens.get(start++));
}
start++;
end++;
}
}
}

private static List tokenize(String S, int offset, int len) {
List tokens = new ArrayList<>();
while (offset + len <= S.length()) {
tokens.add(S.substring(offset, offset+len));
offset += len;
}
return tokens;
}
}
Output:
0
9

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

: 你贴一个code

r*e2015-01-23 08:01

8 楼

看你们贴，那我也贴一个。
public class Solution {
public List findSubstring(String S, String[] L) {

if (S==null||S.length()==0) return Collections.emptyList();

Map map = new HashMap();
Map map_full;
List result= new ArrayList();

for (String s:L){
if (map.containsKey(s)) map.put(s,map.get(s)+1);
else map.put(s,1);
}
int len= L[0].length();
int total=L[0].length()*L.length;

for (int i=S.length();i>=total;i--){

int start=i-l;
map_full=new HashMap(map);
while (start>=0){
String sub=S.substring(start,start+len);

if (!map_full.containsKey(sub)) break;

int count=map_full.get(sub);

if (count==0) break;

map_full.put(sub,count-1);

if (start+total==i) {
result.add(start);
break;
}
start-=len;
}

}
return result;
}
}

y*k2015-01-23 08:01

9 楼

你这个对于
S = "1234123412341234"
L = ["1","2","3","4"]
这种input貌似complexity有点高啊

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

: 看你们贴，那我也贴一个。
: public class Solution {
: public List findSubstring(String S, String[] L) {
:
: if (S==null||S.length()==0) return Collections.emptyList();
:
: Map map = new HashMap();
: Map map_full;
: List result= new ArrayList();
:

r*e2015-01-23 08:01

10 楼

这个还行，就4次重建hashmap
这样比较恶心。

r*e2015-01-23 08:01

11 楼

你那个方法每次循环也得重建一次链表的。这些创建新对象的开销很讨厌，但也没有办
法了。
所以还是得用C＋＋

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

: 你这个对于
: S = "1234123412341234"
: L = ["1","2","3","4"]
: 这种input貌似complexity有点高啊

y*k2015-01-23 08:01

12 楼

我说的是每个start需要scan的位数
你在这个case下每个start都要扫4位
但实际上只需要看上一次scan的开头(或末尾)一位,和这一次scan新扫进来的一位
如果S长度为n,L是k个长度为1的list
你的code worst case要扫 kn 位 (就是我给的例子)
而optimal的应该只需要扫 2n 位, 跟 k 无关

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

: 这个还行，就4次重建hashmap
: 这样比较恶心。

r*e2015-01-23 08:01

13 楼

有道理啊。我有空改一下。
如此这般，那就可以不用每次都创建一个hashmap了。

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

: 我说的是每个start需要scan的位数
: 你在这个case下每个start都要扫4位
: 但实际上只需要看上一次scan的开头(或末尾)一位,和这一次scan新扫进来的一位
: 如果S长度为n,L是k个长度为1的list
: 你的code worst case要扫 kn 位 (就是我给的例子)
: 而optimal的应该只需要扫 2n 位, 跟 k 无关

b*72015-01-23 08:01

14 楼

how about build suffix tree, then string match?

m*k2015-01-23 08:01

15 楼

https://oj.leetcode.com/problems/minimum-window-substring/
变种吧

z*02015-01-23 08:01

16 楼

进facebook了么？

same

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

: 如果onsite你能几分钟写出来bug free 的code？
: You are given a string, S, and a list of words, L, that are all of the same
: length. Find all starting indices of substring(s) in S that is a
: concatenation of each word in L exactly once and without any intervening
: characters.
: For example, given:
: S: "barfoothefoobarman"
: L: ["foo", "bar"]
: You should return the indices: [0,9].