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].(order does not matter).
A:
哦，这道题，一开始是理解错了题目意思了。
仔细研读要求。是对每一个substring,例如从0 开始的，还有从9开始的substring（长度为L的总长度）， 里面包含了L里的所有的non-intervening 组合。就是把所有的L的string连起来。
例如，上面例子中从0 开始的: barfoo 就是L的一个组合。 同样，从9开始的，foobar 也是一个组合。
假设L 里一共有n个string，每个string 长度为 m
分析：
1：我们不能穷尽L的组合形式。 2^n
2: 我们如果从每一个节点都开始计算L， 有点儿太啰嗦的感觉。 想想有没有什么好方法，来跳过部分预先监测的结果。
3： NOTE: strings in L， might exist replication.
4: 初步设想，用一个 list 记录所有match 的节点。然后看后面的substring是否match。 这样，问题就归结于该list里面的值，是否能凑够0到n-1个match。--------但这里有个问题，就是L中 可能有重复的情况。需要注意对待。
（问题就归结到，一个list，每个点包含了match的位置，如果全部的，都有0到n-1都能match的话，就加入result中，否则 移动到下一个点。）
class Solution:
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
res = []
import copy
if len(words) == 0:
return res
wLen = len(words[0])
origD = {} # cannot use set(), since words might have duplicates
for w in words:
self.add2Dict(w,origD)
for i in range(wLen):
D = copy.deepcopy(origD)
foundD = {}
# check every possible starting position, to see whether it is a match
startIndex = i # the index that not valid
for end in range(i, len(s) - wLen +1, wLen):
# continue adding, till we find a match
substr = s[end:end+wLen]
if substr in D: # in original dict
self.add2Dict(substr,foundD)
self.removeD(substr,D)
if len(D) == 0:
res.append(startIndex)
topStr = s[startIndex: startIndex + wLen]
self.add2Dict(topStr, D)
self.removeD(topStr,foundD)
startIndex += wLen
elif substr in foundD: # found, but have been removed before
while s[startIndex: startIndex+ wLen] != substr:
ss = s[startIndex: startIndex+wLen]
self.add2Dict(ss,D)
self.removeD(ss,foundD)
startIndex += wLen
startIndex += wLen
else: # not in words at all, reset the whole
startIndex = end + wLen # next position is a good (or loop till right)
self.addD1toD2(foundD,D)
return res
def removeD(self, word, D):
if D[word] == 1:
del D[word]
else:
D[word] = D[word] -1
def add2Dict(self, word, D):
if word not in D:
D[word] = 1
else:
D[word] = D[word] + 1
def addD1toD2(self, D1, D2): # merge two dict, into D2
for k in D1:
self.add2Dict(k,D2)
D1.clear()
------------------------------4th pass----------------------------
思路： 因为允许重复，所以要记录下出现的次数，因此需要用HashMap.
而这次，为了加速，我们在最外边的循环中，用了 基于各个起始点的位置。
public class Solution {
public List<Integer> findSubstring(String S, String[] L) {
List<Integer> list = new LinkedList<Integer>();
if(S==null || L == null | S.length()==0 || L.length == 0)
return list;
// note that L might contains duplicates
int n = S.length(), m = L[0].length(), k = L.length;
HashMap<String, Integer> origMap = new HashMap<String,Integer>();
for(int i= 0;i<L.length;i++){
String str = L[i];
int count = 1;
if( origMap.containsKey(str)){
count += origMap.get(str);
}
origMap.put(str,count);
}
for(int i =0;i<m;i++){ // for each possible starting position
HashMap<String,Integer> tmpMap = new HashMap<String, Integer>();
int j = i;
while( j<= n-m ){
// remove the oldest
if( j-m*k>=0 ){
String oldStr = S.substring(j-m*k,j-m*k+m);
if(tmpMap.containsKey(oldStr)){
if(tmpMap.get(oldStr)>1){
tmpMap.put(oldStr,tmpMap.get(oldStr)-1);
}else{
tmpMap.remove(oldStr);
}
}
}
// add the newest
String newStr = S.substring(j,j+m);
int nFind = 1;
if(tmpMap.containsKey(newStr)){
nFind += tmpMap.get(newStr);
}
tmpMap.put(newStr,nFind);
// check if it is match
boolean isAllFind = true;
for(String str : origMap.keySet()){
if(tmpMap.containsKey(str)== false || tmpMap.get(str)!=origMap.get(str)){
isAllFind = false;
break;
}
}
if(isAllFind)
list.add(j-m*k+m);
//update j
j+=m;
}
}
return list;
}
}
--------------------第二遍----------- AC 了 --------
思路就是： 既然允许有重复， 而且， 还要尽量快， 用Set是不太行了。 那就用HashMap， 来记录下 每个key的出现的次数。
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> al = new ArrayList<Integer>();
if (S == null || L == null || S.length() == 0 || L.length == 0)
return al;
// make a set from L, so that we can
int nL = L.length;
int mL = L[0].length();
for (int k = 0; k <= S.length() - nL * mL; k++) {
Map<String, Integer> map = buildSet(L);
String curS = S.substring(k, k + mL * nL);
int i = 0;
int matchedCount = 0;
while (matchedCount < nL) {
String tmp = curS.substring(i, i + mL);
if (map.containsKey(tmp)) {
int count = map.get(tmp);
if(count <=0)
break;
map.put(tmp, count - 1);
i += mL;
matchedCount++;
} else
break;
}
// iterator all the list, to see whether it has been fully visited
boolean isAllFind = true;
for(String key : map.keySet())
if(map.get(key)>0){
isAllFind = false;
break;
}
if(isAllFind)
al.add(k);
}
return al;
}
private Map<String, Integer> buildSet(String[] L) {
Map<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < L.length; i++) {
if (map.containsKey(L[i])) {
int count = map.get(L[i]);
map.put(L[i], count + 1);
} else
map.put(L[i], 1);
}
return map;
}
}
Mistakes:
----------------第二遍------开始理解错题意了。
1： 所谓的withougt any interleaving characters,是指一个 concatenation里面不能interleaving. 但是，多个，是可以的。
2： 输入的 L 可以是["a","b","a"] ， 因此，不能用Set 来存储。
Learned:
---------------3 rd 想利用每个L 中的 string 映射到一个HashMap上去。------------
思想很简单， 和楼上的那个通不过的方法如出一致。-------------其实就是第二遍的思想。-------
就是对每个string in L ,map 一个数值。 作为标记。 然后，看其是否在map中出现过，如果出现过，对比出现的次数。
但是，还是suffer了这样一个问题， 就是L 中有重复的情况。
因此，我们还需要记录在L中出现的次数。 作为参照物，还要记录用过的次数。
因此，我们自己定义了一个类。
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> al = new ArrayList<Integer>();
int n = L.length;// assume n > 0
int l = L[0].length();
HashMap<String, SNode> map = new HashMap<String, SNode>();
int nDifferent=0; // number of different Strings in L
for(int i =0;i< n;i++){
SNode node = map.get(L[i]);
if(node == null){
nDifferent++;
node = new SNode(nDifferent);
map.put(L[i],node);
}else
node.count++;
}
// for each position, calculate its total sum
for(int i =0;i<= S.length() - l*n; i++){
for(int j =0;j< n;j++) // reset all
map.get(L[j]).nUsed=0;
// test sum of these String
boolean isBreak = false;
for(int k = 0;k<n;k++){
String str= S.substring(i+k*l, i+(k+1)*l);
SNode node = map.get(str);
if(node == null || node.nUsed>=node.count){
isBreak = true;
break;
}else{
node.nUsed++;
}
}
if(!isBreak)
al.add(i);
}
return al;
}
}
class SNode{
public int val;
public int count;
public int nUsed=0; // number of used
public SNode(int v){
val = v;
count = 1;
}
}
No comments:
Post a Comment