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).
思路:用一个hashmap保存链表L,对S进行扫描,若每个子单词在L中出现且仅出现一次,则满足条件。
public class Solution { public ArrayList<Integer> findSubstring(String S, String[] L) { ArrayList<Integer> ret = new ArrayList<Integer>(); if (S == null || L == null) { return ret; } int length_words = L[0].length(); int length_list = L.length; int length_str = length_words*length_list; HashMap<String, Integer> list_words = new HashMap<String, Integer>(); for (String word : L) { if (!list_words.containsKey(word)) { list_words.put(word, 1); } else list_words.put(word, list_words.get(word)+1); } for (int i = 0; i <= S.length()-length_str; i++) { String tmp = S.substring(i, i+length_str); HashMap<String, Integer> tmp_hashHashMap = (HashMap<String, Integer>)list_words.clone(); int j; for (j = 0; j < length_list; j++) { String tmpword = tmp.substring(j*length_words, j*length_words+length_words); if (!tmp_hashHashMap.containsKey(tmpword)) { break; } else if (tmp_hashHashMap.get(tmpword) <= 0) { break; } else tmp_hashHashMap.put(tmpword, tmp_hashHashMap.get(tmpword)-1); } if (j == length_list) { ret.add(i); } } return ret; } }
【LeetCode】Substring with Concatenation of All Words,布布扣,bubuko.com
【LeetCode】Substring with Concatenation of All Words
原文:http://blog.csdn.net/xiaozhuaixifu/article/details/24919889