I*******g
发帖数: 7600 | 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***k
发帖数: 162 | | I*******g
发帖数: 7600 | 3 你贴一个code
【在 y***k 的大作中提到】
: 中上吧.
: 不算太难
| r*******e
发帖数: 971 | | k*******a
发帖数: 433 | | c*****m
发帖数: 271 | 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***k
发帖数: 162 | 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; offset
searchInTokens(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*******e
发帖数: 971 | 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***k
发帖数: 162 | 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*******e
发帖数: 971 | 10 这个还行，就4次重建hashmap
这样比较恶心。 | | | r*******e
发帖数: 971 | 11 你那个方法每次循环也得重建一次链表的。这些创建新对象的开销很讨厌，但也没有办
法了。
所以还是得用C＋＋
【在 y***k 的大作中提到】
: 你这个对于
: S = "1234123412341234"
: L = ["1","2","3","4"]
: 这种input貌似complexity有点高啊
| y***k
发帖数: 162 | 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*******e
发帖数: 971 | 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*****7
发帖数: 31 | 14 how about build suffix tree, then string match? | m*****k
发帖数: 731 | | z****0
发帖数: 4413 | 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].
|
|
