问题描述
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9]. (order does not matter).
问题分析
这道题是给了我们一个长字符串和一组长度相同的word，将这个words中的字符串拼接并在字符串s里找到所有拼接字符串的下标。
算法描述
将words创建一个hashmap 并计数，从s的下标0开始遍历，每一次将后面len长度的字符串在map中寻找，找到一个将映射值减一，直到map为空则说明这个下标对应的字符串是words的拼接字符串，若其中有一次不存在，则直接break，下标向后移动。直到遍历完成为止，返回得到的下标列表。
java实现
import java.util.*;
public class SubstringwithConcatenationofAllWords {
public static List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
if (s == null || words == null || words.length == 0) return res;
int len = words[0].length(); // length of each word
Map<String, Integer> map = new HashMap<>(); // map for L
for (String w : words) {
map.put(w, map.containsKey(w) ? map.get(w) + 1 : 1);
}
for (int i = 0; i <= s.length() - len * words.length; i++) {
Map<String, Integer> copy = new HashMap<>(map);
for (int j = 0; j < words.length; j++) { // checkc if match
String str = s.substring(i + j*len, i + j*len + len); // next word
if (copy.containsKey(str)) { // is in remaining words
int count = copy.get(str);
if (count == 1)
copy.remove(str);
else
copy.put(str, count - 1);
if (copy.isEmpty()) { // matches
res.add(i);
break;
}
}
else
break; // not in L
}
}
return res;
}
}
总结
善于将问题转化。
转载于:https://www.cnblogs.com/lyf722/p/7760911.html
相关资源：JAVA上百实例源码以及开源项目
