给出一个字符串S和一组单词L，L中单词的长度都相等，找出S中的符合以下要求的子串在S中的起始位置索引：子串为L中所有单词串联在一起(单词的顺序随意)，L中的每个单词只出现一次，中间不能有其他的字符。
例如：给定S="nowcoderacodnowert"，L为["now", "cod"]，
返回的索引应该是[0,9].（不用关心给出索引的顺序）
[编程题]索引所有子串
/**
* 30. Substring with Concatenation of All Words
*
* @author Administrator
*
* 题意：给定一个字符串S和一个字符串数组L，L中的字符串长度都相等， 找出S中所有的子串恰好包含L中所有字符各一次，返回子串的起始位置。
* 该题与leetcode 3.Longest Substring Without Repeating Characters类似
*
*/
public class Demo1 {
/*
* 超时边缘的解法：Runtime: 211 ms
* 该方法可以通过牛客网，但是在leetcode提交的时候有时候会超时
*/
public ArrayList<Integer> findSubstring(String s, String[] words) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (s == null || words == null || words.length * words[0].length() > s.length())
return res;
//map中的key是字符串，value记录字符串在words中出现的的次数
Map<String,Integer> map=new HashMap<String,Integer>();
Map<String,Integer> tmpMap=new HashMap<String,Integer>();
int wordNum=words.length,wordLen=words[0].length();
//考虑到words中可能会有重读的字符串
for(int i=0;i<wordNum;i++){
if(tmpMap.containsKey(words[i]))
tmpMap.put(words[i], tmpMap.get(words[i])+1);
else
tmpMap.put(words[i], 1);
}
for(int i=0;i<=s.length()-wordNum*wordLen;i++){
map.clear();
//用空间换时间
int index=i;
int count=0;
for(int j=0;j<words.length;j++){
String temp=s.substring(index, index+wordLen);
if(!tmpMap.containsKey(temp))
break;
if(map.containsKey(temp))
map.put(temp, map.get(temp)+1);
else
map.put(temp, 1);
if(map.get(temp)>tmpMap.get(temp))
break;
count++;
index+=wordLen;
}
if(count==wordNum)
res.add(i);
}
return res;
}
}
编辑于 2017-07-20 12:13:27
回复(0)
更多回答
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> counts;//存储每个单词的次数
for (string word : words)
counts[word]++;
int n = s.length(), num = words.size(), len = words[0].length();
vector<int> indexes;
for (int i = 0; i < n - num * len + 1; i++) {
//i代表起点
unordered_map<string, int> seen;//存储i为起点的字符串里指定单词的次数
int j = 0;//表示单词数目，只有当j==num时，才找到了所有单词
for (; j < num; j++) {
string word = s.substr(i + j * len, len);//以i为起点，长度为len的第j个单词
if (counts.find(word) != counts.end()) {
seen[word]++;
if (seen[word] > counts[word])//如果此单词出现次数超出，则i位置不合法
break;
}
else break;//如果此单词不存在于counts里，i位置不合法
}
if (j == num) indexes.push_back(i);//i==num，则i是合法位置之一
}
return indexes;
}
发表于 2017-07-04 09:58:40
回复(5)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> indexs = new ArrayList<Integer>();
Map<String, Integer> map_L = new HashMap<String, Integer>();
Map<String, Integer> map_temp = new HashMap<String, Integer>();
int wordsnum = L.length,
wordlen = L[0].length();
for (String str : L) {
if(map_L.containsKey(str)){
map_L.put(str, map_L.get(str)+1);
}else{
map_L.put(str, 1);
}
}
for(int i = 0 ; i < S.length()-wordsnum*wordlen+1; i++){
int count = 0;
map_temp.clear();
for(int j = i;j<wordsnum*wordlen+i;j+=wordlen){
String tmp = S.substring(j, j+wordlen);
if(map_L.containsKey(tmp)){
if(map_temp.containsKey(tmp)){
map_temp.put(tmp, map_temp.get(tmp)+1);
}else{
map_temp.put(tmp, 1);
}
count++;
}else{
break;
}
if(map_temp.get(tmp)>map_L.get(tmp)){
break;
}
if(count == wordsnum){
indexs.add(i);
}
}
}
return indexs;
}
}
发表于 2017-07-31 19:29:48
回复(0)
//说好的order does not matter,最后怎么还是需要按照从小到达的顺序呢？ public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (S==null||S.length()==0||L==null||L.length==0){
return res;
}
HashMap<String,Integer> dict = new HashMap<String,Integer>();
int word_len=L[0].length();
for(String word:L){
if(dict.containsKey(word)){
dict.put(word, dict.get(word)+1);
}else{
dict.put(word, 1);
}
}
for(int i=0;i<word_len;i++){
int count =0;//计算出现的单词的个数
int index =i;
HashMap<String,Integer> win = new HashMap<String,Integer>();
for(int j=i;j<=S.length()-word_len;j+=word_len){
String tmp = S.substring(j,j+word_len);
if(dict.containsKey(tmp)){//如果值出现在集合里
if(win.containsKey(tmp)){//如果值出现在窗口里
win.put(tmp, win.get(tmp)+1);
}else{
win.put(tmp,1);
}
if(win.get(tmp)<=dict.get(tmp)){
count++;
}else{
while(win.get(tmp)>dict.get(tmp)){
String s=S.substring(index,index+word_len);
win.put(s, win.get(s)-1);
if(win.get(s)<dict.get(s)){
count--;
}
index=index+word_len;
}
}
if(count==L.length){
res.add(index);
String s1= S.substring(index,index+word_len);
win.put(s1, win.get(s1)-1);
index = index+word_len;
count--;
}//j结束
}else{//如果不出现在集合里，那么将要从窗口最右面重新开始
win.clear();
count=0;
index=j+word_len;
}
}
}//i结束
Collections.sort(res);//为什么必须排序后才通过呢？
return res;
}
}
编辑于 2016-11-03 18:17:40
回复(1)
class Solution {
public:
vector<int> findSubstring(string S, vector<string> &L) {
map<string,int> M;
vector<int> v;
for(string s: L)
M[s]++;
int n = S.size();
int m = L.size();
int l = L[0].size();
for(int i=0;i<n-m*l+1;i++)
{
map<string,int> T;
int k = 0;
for(;k<m;k++)
{
string s = S.substr(i+k*l,l);
if(M.find(s) != M.end())
{
T[s]++;
if(T[s] > M[s])
break;
}else
break;
}
if(k == m)
v.push_back(i);
}
return v;
}
};
发表于 2017-09-14 00:45:13
回复(0)
//字符串的模式匹配变型 /*1）L中存在重复的元素2）子串不允许间断，即子串从开始到找全L中的所有元素之前，子串中不允许包含L以外的东西，而且，即使当前处理的子串是L中含有的，但是前面已经找够了，这个多余的也是不合法的，若此时还有L中的其他元素没找到，从这个起点开始也是不成功的。
3）L在S中出现的顺序不同考虑，任意顺序，只要全部存在就可以。
分析：
1）先对L中的所有元素做个统计，定义一个hash map<string, int> 型 变量total，统计每个词出现的次数，另外定义一个同类型的count，用来记录到目前为止，已经找到的L中的元素情况，当全部找全的时候就找到了一个合法的起始点。然后将count清空，继续找。
2）整体的框架与传统的字符串匹配一致，不同的是这里不要求顺序，所以似乎在S中不能加速移动。*/
import java.util.*; public class Solution { public ArrayList<Integer> findSubstring(String s, String[] strs) { ArrayList<Integer> array=new ArrayList(); if(s == null||s.length() == 0||strs == null||strs.length == 0||s.length() < strs[0].length()){ return array; } HashMap<String,Integer> map=new HashMap(); for(int i=0;i<strs.length;i++){//统计每个串出现的次数 if(!map.containsKey(strs[i])){ map.put(strs[i],1); }else{ map.put(strs[i],map.get(strs[i])+1); } } HashMap<String,Integer> count;//暂时统计出现次数 int inlen=strs[0].length(); int dstlen=inlen*strs.length; for(int i=0;i <= s.length()-dstlen;i++){ int j=i; count=new HashMap(); int cur=0; for(;cur<strs.length;cur++){ String curstr=s.substring(j,j+inlen); if(!map.containsKey(curstr)){ break; } if(!count.containsKey(curstr)){ count.put(curstr,1); }else if(count.get(curstr) < map.get(curstr)){ count.put(curstr,count.get(curstr)+1); }else{ break; } j=j+inlen; } if(cur == strs.length){ array.add(i); } } return array; } }
编辑于 2016-08-13 15:46:38
回复(0)
题意：给定一个字符串S和一个字符串数组L，L中的字符串长度都相等，找出S中所有的子串恰好包含L中所有字符各一次，返回子串的起始位置。
思路：
定义一个哈希表count用来记录words的个数；
遍历string的每一个字符s[i]，停止条件是当剩余的字符个数少于words中的字符个数：
定义另一个哈希表seen，用来记录遍历出的子串
j循环nums次，nums代表words中单词的个数
取出以i + j * len 为首字符，长度为len的子串，在count中寻找是否存在
若存在，记录出现的次数，并与count中对比，大于则以 i 开始的子串非法
若不存在，同样以 i 开始的子串非法
记录此时的索引 i
class Solution {
public:
vectorfindSubstring(string s, vector& words) {
unordered_map<string> counts;//存储每个单词的次数
for (string word : words)
counts[word]++;
int n = s.length(), num = words.size(), len = words[0].length();
vectorindexes;
for (int i = 0; i < n - num * len + 1; i++) {
//i代表起点
unordered_map<string> seen;//存储i为起点的字符串里指定单词的次数
int j = 0;//表示单词数目，只有当j==num时，才找到了所有单词
for (; j < num; j++) {
string word = s.substr(i + j * len, len);//以i为起点，长度为len的第j个单词
if (counts.find(word) != counts.end()) {
seen[word]++;
if (seen[word] > counts[word])//如果此单词出现次数超出，则i位置不合法
break;
}
else break;//如果此单词不存在于counts里，i位置不合法
}
if (j == num) indexes.push_back(i);//i==num，则i是合法位置之一
}
return indexes;
}
};</string></string>
发表于 2019-05-26 19:09:59
回复(0)
感觉自己写的很复杂，但是应该思路比较清晰。我们应该用hash_map来保存我们L中的元素，这样可以减少查找复杂度，每次查找完（得到一个完整匹配），都要将hash_map中的值恢复为原值用于下次查找，原因是在查找计数过程中需要更改hash_map中的值，感觉这里可以优化。
unordered_map<string, int> dict, c_dict;
int len = L[0].size(); vector<int> res;
if (S.empty() || L.empty() || S.size() < len * L.size()) return res;
for (int i = 0; i < L.size(); ++i)
{
if (dict.find(L[i]) != dict.end())
dict[L[i]]++;
else
dict[L[i]] = 1;
}
c_dict = dict;
int count = 0, num = L.size();
for (int i = 0; i <= S.size() - len * num; ++i)
{
string word = S.substr(i, len * num); dict = c_dict; count = 0;
for (int j = 0; j <= word.size() - len; j += len)
{
string str = word.substr(j, len);
if (dict.find(str) != dict.end())
{
if (dict[str] > 0)
{
dict[str]--; count++;
}
else break;
}
else break;
}
if (count == num) res.push_back(i);
}
return res;
发表于 2018-03-28 11:42:39
回复(0)
import java.util.*;
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> res = new ArrayList<Integer>();
Map<String, Integer> map;
int len = L[0].length(), strLen = len * L.length;
for (int i = 0; i <= S.length() - strLen; i++) {
map = new HashMap<>();
for (int k = 0; k < L.length; k++) {
if (map.containsKey(L[k]))
map.replace(L[k], map.get(L[k]) + 1);
else
map.put(L[k], 1);
}
int cnt = 0, j = i;
while (cnt < L.length) {
String word = S.substring(i + len * cnt, i + len * (cnt + 1));
Integer val = map.get(word);
if (val == null || val == 0)
break;
else map.replace(word, map.get(word) - 1);
cnt++;
}
if (cnt == L.length)
res.add(i);
}
return res;
}
}
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> res = new ArrayList<Integer>();
Map<String, Integer> map;
int len = L[0].length(), strLen = len * L.length;
for (int i = 0; i <= S.length() - strLen; i++) {
map = new HashMap<>();
for (int k = 0; k < L.length; k++) {
if (map.containsKey(L[k]))
map.replace(L[k], map.get(L[k]) + 1);
else
map.put(L[k], 1);
}
int cnt = 0, j = i;
while (cnt < L.length) {
String word = S.substring(i + len * cnt, i + len * (cnt + 1));
Integer val = map.get(word);
if (val == null || val == 0)
break;
else map.replace(word, map.get(word) - 1);
cnt++;
}
if (cnt == L.length)
res.add(i);
}
return res;
}
}
发表于 2020-09-30 10:41:02
回复(0)
import java.util.*;
public class Solution {
/*
将问题分解开（那么需要解决以下几个问题）：
（1）怎么解决L中单词重复的问题；
（2）怎么判断连续的字串是L中的单词
*/
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> list = new ArrayList<>();
if(S.equals("")||S==null||L==null||L.length==0)
return list;
int len = L.length;
int strLen = L[0].length();
int totalLen = len*strLen;
int index = 0;
int end = index+totalLen;
while(index<S.length()&&end<=S.length()){
boolean[] flag = new boolean[len];//布尔数组为了解决L字符串数组中单词重复的问题
int num = 0;
for(int i=index;i<end;i+=strLen){
String str = S.substring(i,i+strLen);
int j=0;
for(;j<len;j++){//不能将判断条件!flag[j]放到循环的判断中，因为一旦条件不符合循环就会退出，不会再继续进行判断
if(!flag[j]&&str.equals(L[j])){
flag[j]=true;
num++;
break;
}
}
if(j==len)
break;
}
if(num==len)
list.add(index);
index++;
end = index+totalLen;
}
return list;
}
}
发表于 2020-06-11 10:59:31
回复(0)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
Map<String, Integer> wordMap = new HashMap<>();
for (String item : L) {
if (wordMap.containsKey(item)) {
wordMap.put(item, wordMap.get(item) + 1);
} else {
wordMap.put(item, 1);
}
}
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i <= S.length() - L[0].length() * L.length; i++) {
Map<String, Integer> matchMap = new HashMap<>();
for (int matchNum = 0; matchNum < L.length; ) {
String word = S.substring(L[0].length() * matchNum + i, L[0].length() * (matchNum + 1) + i);
if (!wordMap.containsKey(word)) {
break;
} else {
if (matchMap.containsKey(word)) {
matchMap.put(word, matchMap.get(word) + 1);
} else {
matchMap.put(word, 1);
}
if (matchMap.get(word) > wordMap.get(word)) {
break;
}
if (++matchNum == L.length) {
result.add(i);
}
}
}
}
return result;
}
}
发表于 2019-09-25 23:54:06
回复(0)
vector<int> findSubstring(string S, vector<string> &L) {
vector<int>ans;
int len = S.size();
int mem = L.size();
if(!mem||!len)return ans;
int len_L = L[0].size();
unordered_map<string,int>mp;
for(int i=0;i<mem;++i)mp[L[i]]++;
for(int i=0;i<=len-len_L*mem;++i){
unordered_map<string,int>mptmp = mp;
int cnt = mem;
string tmp = S.substr(i,len_L);
int j,index = i;
for(j=i;j<=len-len_L&&mptmp[tmp];j = j+len_L,tmp =S.substr(j,len_L)){
cnt--;
mptmp[tmp]--;
}
if(cnt==0)ans.push_back(index);
}
return ans;
}
发表于 2019-08-20 22:42:01
回复(0)
class Solution {
public:
vector<int> findSubstring(string S, vector<string> &L) {
vector<int> result;
if(S.empty()||L.empty()||S.size()<L[0].size()*L.size())
return result;
int sub = L[0].size();
int lengthS = S.size();
int len = L.size();
unordered_map<string,int> dict;
for(int i=0; i<len; i++){
dict[L[i]]++;
}
for(int i=0; i<lengthS - sub*len+1; i++){
unordered_map<string,int> seen;
int j=0;
for(; j<len; j++){
string word = S.substr(i+j*sub, sub);
if(dict.find(word) != dict.end()){
seen[word]++;
if(seen[word]>dict[word])
break;
}
else
break;
}
if(j==len)
result.push_back(i);
}
return result;
}
};
public:
vector<int> findSubstring(string S, vector<string> &L) {
vector<int> result;
if(S.empty()||L.empty()||S.size()<L[0].size()*L.size())
return result;
int sub = L[0].size();
int lengthS = S.size();
int len = L.size();
unordered_map<string,int> dict;
for(int i=0; i<len; i++){
dict[L[i]]++;
}
for(int i=0; i<lengthS - sub*len+1; i++){
unordered_map<string,int> seen;
int j=0;
for(; j<len; j++){
string word = S.substr(i+j*sub, sub);
if(dict.find(word) != dict.end()){
seen[word]++;
if(seen[word]>dict[word])
break;
}
else
break;
}
if(j==len)
result.push_back(i);
}
return result;
}
};
发表于 2019-08-08 21:36:14
回复(0)
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> result = new ArrayList<>();
if(S==null||L==null||L.length==0){
return result;
}
int len = L.length;
int wordLen = L[0].length();
for(int i=0;i<wordLen;i++){
ArrayList<String> subList = new ArrayList<>();
for(int j=i;j<S.length()-wordLen+1;j = j+wordLen){
String sub = S.substring(j,j+wordLen);
subList.add(sub);
}
for(int k : findSubstring(subList,L,len)){
result.add(i+k*wordLen);
}
}
result.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1-o2;
}
});
return result;
}
private ArrayList<Integer> findSubstring(ArrayList<String> list,String[] L,int size){
ArrayList<Integer> result = new ArrayList<>();
HashMap<String,Integer> map = createMap(L);
int left = 0;
int count = size;
for(int i = 0;i<list.size();i++){
String str = list.get(i);
if(!map.containsKey(str)){
while (left<i){
String key = list.get(left);
map.put(key,map.get(key)+1);
left++;
count++;
}
left = i+1;
}else if(map.get(str)==0){
while (!str.equals(list.get(left))){
String key = list.get(left);
map.put(key,map.get(key)+1);
left++;
count++;
}
left++;
}else {
map.put(str, map.get(str) - 1);
count--;
if (count == 0) {
result.add(left);
String key = list.get(left);
map.put(key,map.get(key)+1);
left ++;
count ++;
}
}
}
return result;
} 1、因为所有L中所有word都相等，所以可将字符串分割成字符数组 如 barfoothefoobarman
[bar, foo, the, foo, bar, man]
[arf, oot, hef, oob, arm]
[rfo, oth, efo, oba, rma]
2、问题就转换成每个字符串数组中求解
3、将求解结果转换下 i+k*wordLen
4、要求结果从大到小，所以排下序
发表于 2018-08-31 14:41:27
回复(0)
class Solution {
public:
vector<int> out;
map<string,int> book;
vector<int> findSubstring(string S, vector<string> &L) {
out.clear();
book.clear();
if(S.empty()||L.empty())
return out;
int sz=L.size();
int l1=S.length();
int l2=L[0].length();
int l=sz*l2;
for(int i=0;i<sz;i++)
{
if(book.find(L[i])==book.end())
book[L[i]]=0;
book[L[i]]++;
}
for(int i=0;i<=l1-l;i++)
{
map<string,int> bookt=book;
string tm=S.substr(i,l);
int cnt=0;
for(int j=0;j<l;)
{
string tp=tm.substr(j,l2);
j+=l2;
if(bookt.find(tp)==bookt.end())
break;
bookt[tp]--;
if(bookt[tp]<0)
break;
cnt++;
}
if(cnt==sz)
out.push_back(i);
}
return out;
}
};
发表于 2018-06-23 10:38:58
回复(0)
import java.util.*;
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> list = new ArrayList<>();
int interval = L[0].length();
Map<String, Integer> map = new HashMap<>();
for(int i = 0; i < interval; i++){
map.clear();
for(String s1 : L){
map.put(s1, map.getOrDefault(s1, 0) + 1);
}
int left = i;
int right = i;
int counter = map.size();
for(right = i; right <= S.length() - interval; right += interval){
String word = S.substring(right, right + interval);
if(map.containsKey(word)){
map.put(word, map.get(word) - 1);
if(map.get(word) == 0) counter--;
}
if(right - left == L.length * interval){
String temp = S.substring(left, left + interval);
if(map.containsKey(temp)){
map.put(temp, map.get(temp) + 1);
if(map.get(temp) == 1) counter++;
}
left += interval;
}
if(counter == 0 && right - left == (L.length - 1) * interval){
list.add(left);
}
}
}
Collections.sort(list);
return list;
}
}
发表于 2018-04-03 11:16:07
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> r = new ArrayList<Integer>();
if(S == null || S.length() == 0 || L.length == 0 || S.length() < L.length * L[0].length()) return r;
ArrayList<String> t = new ArrayList<>();
for(int i = 0;i < L.length;i++) t.add(L[i]);
for(int i = 0;i <= S.length() - L[0].length();i++){
String tmp = S.substring(i,i+L[0].length());
ArrayList<String> t1 = new ArrayList<>(t);
if(t1.contains(tmp)) {
t1.remove(tmp);
for(int k = i+L[0].length();k <= S.length() - L[0].length();k += L[0].length()){
tmp = S.substring(k,k+L[0].length());
if(t1.contains(tmp)){
t1.remove(tmp);
}
else break;
}
if(t1.size() == 0) r.add(i);
}
}
return r;
}
}
发表于 2018-03-26 21:42:32
回复(0)
class Solution {
public:
vector<int> findSubstring(string S, vector<string> &L) {
int len = S.length();
int n = L.size();
vector<int> result;
if(len == 0 || n == 0)
return result;
int sublen = L[0].length();
int templen = n*sublen;
if(len < templen)
return result;
for(int i = 0;i <= len - templen;i++){
map<string,int> index;
bool flag = true;
for(int j = 0; j < n;j++){
index[S.substr(i+j*sublen,sublen)]++;
// index.insert(make_pair(S.substr(i+j*sublen,sublen),1));
}
for(auto t:L){
if(index.find(t) == index.end()){
flag = false;
break;
}else{
if(index[t] == 0){
flag = false;
break;
}else{
index[t]--;
}
}
}
if(flag)
result.push_back(i);
}
return result;
}
};
发表于 2017-07-28 11:27:15
回复(0)
1）先对L中的所有元素做个统计，定义一个hash map<string, int> 型 变量total，统计每个词出现的次数，
另外定义一个同类型的count，用来记录到目前为止，已经找到的L中的元素情况，
当全部找全的时候就找到了一个合法的起始点。然后将count清空，继续找。
2）整体的框架与传统的字符串匹配一致，不同的是这里不要求顺序，所以似乎在S中不能加速移动
import java.util.*;
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> list = new ArrayList<>();
if(S.length()==0||L.length==0){
return list;
}
int len = L[0].length();
int alllen = L.length*len;
HashMap<String,Integer> map = new HashMap<String,Integer>();
for(int i = 0;i<L.length;i++){
if(map.containsKey(L[i])){
map.put(L[i],map.get(L[i])+1);
}else{
map.put(L[i],1);
}
}
HashMap<String, Integer> count = null;
for(int i =0;i<=S.length()-alllen;i++){
int j = i;
int cur = 0;
count = new HashMap<String,Integer>();
for(;cur<L.length;cur++){
String sub = S.substring(j,j+len);
if(!map.containsKey(sub)){
break;
}
if(count.containsKey(sub)){
if(count.get(sub)<map.get(sub)){
count.put(sub,count.get(sub)+1);
}else{
break;
}
}else{
count.put(sub,1);
}
j = j+len;
}
if(cur == L.length)
{
list.add(i);
}
}
return list;
}
}
发表于 2017-06-08 21:32:37
回复(0)
import java.util.ArrayList;
import java.util.HashMap;
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> list=new ArrayList<>();
HashMap<String,Integer> dict=new HashMap<>();
HashMap<String,Integer> result=new HashMap<>();
int m=L.length;
int n=L[0].length();
int len=S.length();
for(String ss:L){
if(!dict.containsKey(ss)){
dict.put(ss,1);
}else{
dict.put(ss,dict.get(ss)+1);
}
}
for(int i=0;i<=len-m*n;++i){
result.clear();
int j;
for( j=0;j<m;++j){
int k=i+j*n;
String str=S.substring(k,k+n);
if(!dict.containsKey(str))
break;
if(result.containsKey(str)){
result.put(str,result.get(str)+1);
}else{
result.put(str,1);
}
if(result.get(str)>dict.get(str))
break;
}
if(j==m)
list.add(i);
}
return list;
}
}
发表于 2017-04-14 10:49:06
回复(0)
问题信息
难度：
26条回答
53收藏
15561浏览
通过挑战的用户
查看代码-
2023-02-28 16:59:33
-
2022-08-16 22:13:17
-
2022-06-24 09:39:09
-
2022-05-15 12:36:57
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
