首页 > 代码库 > [leetcode] Substring with Concatenation of All Words
[leetcode] Substring with Concatenation of All Words
题目：（HashTable，Two Point）
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).
题解：
看代码思路还是很清晰的就是顺着给的string s，找。不过不是找一个字母，而是找一个单词，然后L里面的所有单词又刚好都要来一遍。
public class Solution { public ArrayList<Integer> findSubstring(String S, String[] L) { HashMap<String, Integer> Lmap = new HashMap<String, Integer>(); HashMap<String, Integer> Smap = new HashMap<String, Integer>(); ArrayList<Integer> result = new ArrayList<Integer>(); int total = L.length; if(total==0) return result; for(int i=0;i<total;i++) { if(!Lmap.containsKey(L[i])) Lmap.put(L[i], 1); else { int k = Lmap.get(L[i]); Lmap.put(L[i], k+1); } } int len = L[0].length(); for(int i=0;i<=S.length()-len*total;i++) { Smap.clear(); int j = 0; for(;j<total;j++) { String s = S.substring(i+j*len, i+(j+1)*len); if(!Lmap.containsKey(s)) break; if(!Smap.containsKey(s)) Smap.put(s, 1); else { int k = Smap.get(s); Smap.put(s, k+1); } if(Smap.get(s)>Lmap.get(s)) break; } if(j==total) { result.add(i); } } return result; }}
[leetcode] Substring with Concatenation of All Words
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。