首页 > 代码库 > Substring with Concatenation of All Words
Substring with Concatenation of All Words
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).
对于这道题，有几个关键信息，1.每个单词的长度为定长，2.L中可能会有重复的单词
因此可以构建一个HashMap,用来保存L中单词及出现的次数，之后因为单词个数与长度都确定了，因此可以从S字符串中每次取出该定长的子字符串用来做对比，
1.看看该子字符串是否包含连续的单词
2.看看是否每个单词都出现了，且出现的个数和HashMap中一致，如果是，就添加该起始位置
1 package Substring.with.Concatenation.of.All.Words; 2 3 import java.util.ArrayList; 4 import java.util.HashMap; 5 import java.util.List; 6 import java.util.Map; 7 8 public class SubstringWithConcatenationofAllWords { 9 public List<Integer> findSubstring(String S, String[] L) {10 //最终结果11 List<Integer> list=new ArrayList<Integer>();12 //词典，用来保存L中出现的单词及次数13 Map<String,Integer> dictionary=new HashMap<String,Integer>();14 int wordsNum=L.length;15 int wordLen=L[0].length();16 int totalLen=wordsNum*wordLen;17 //将L中的单词放在dictionary中18 for(int i=0;i<wordsNum;i++){19 if(dictionary.containsKey(L[i])){20 int num=dictionary.get(L[i]);21 num=num+1;22 dictionary.put(L[i], num);23 }else{24 dictionary.put(L[i], 1);25 }26 }27 //查找起始点28 29 for(int i=0;i<=S.length()-totalLen;i++){30 String ss=S.substring(i,i+totalLen);31 Map<String,Integer> currMap=new HashMap<String,Integer>();32 while(true){33 String subStr=ss.substring(0,wordLen);34 if(dictionary.containsKey(subStr)){35 if(currMap.containsKey(subStr)){36 int num=currMap.get(subStr);37 currMap.put(subStr,num+1 );38 if(num+1>dictionary.get(subStr)){39 break;40 }41 }else{42 currMap.put(subStr, 1);43 }44 ss=ss.substring(wordLen);45 if(ss.isEmpty()){46 for(Map.Entry<String, Integer> entry:dictionary.entrySet()){47 String currStr=entry.getKey();48 int num=entry.getValue();49 if(currMap.get(currStr)==null||num!=currMap.get(currStr)){50 break;51 }52 }53 list.add(i);54 break;55 }56 }else{57 break;58 }59 }60 }61 return list;62 }63 public static void main(String args[]){64 String S="aaa";65 String []L={"a","b"};66 SubstringWithConcatenationofAllWords service=new SubstringWithConcatenationofAllWords();67 List<Integer>list=service.findSubstring(S, L);68 for(int a:list){69 System.out.println(a);70 }71 }72 }
Substring with Concatenation of All Words
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。