Java for LeetCode 030 Substring with Concatenation of All Words【HARD】

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).

解题思路：

由于涉及到对words的查询

因此第一步：将words[] put进图里，key代表单词，value代表单词次数。

考虑到s很长，一步一步走的话其实有很多时候可以利用之前的结果，因此可以以word[0].length为单位进行一次遍历（类似于奇偶），这样就可以使用前面的结果了。

然后设一个指针，每次移动word[0].length步，检查是否在words的图里面，如果有的话，也把它放到另外一张图里面，并引用一个计数器，如果计数器长度和words[].length的长度一致的话，那么找到一组解，指针后移。当然，里面有很多判断条件，具体见代码，JAVA实现：

	static public List<Integer> findSubstring(String s, String[] words) {

		List<Integer> list = new ArrayList<Integer>();

		if (s.length() == 0 || words.length == 0 || words[0].length() == 0)

			return list;

		HashMap<String, Integer> wordsMap = new HashMap<String, Integer>();

		for (String string : words) {

			if (!wordsMap.containsKey(string))

				wordsMap.put(string, 1);

			else

				wordsMap.put(string, wordsMap.get(string) + 1);

		}

		for (int i = 0; i < words[0].length(); i++) {

			int StartIndex = i, wordsLength = 0;

			HashMap<String, Integer> tmap = new HashMap<String, Integer>();

			for (int j = i; j <= s.length() - words[0].length(); j += words[0].length()) {

				String str = s.substring(j, j + words[0].length());

				if (wordsMap.containsKey(str)) {

					if (tmap.containsKey(str))

						tmap.put(str, tmap.get(str) + 1);

					else

						tmap.put(str, 1);

					wordsLength++;

					while (tmap.get(str) > wordsMap.get(str)) {

						String startWord = s.substring(StartIndex,StartIndex + words[0].length());

						StartIndex += words[0].length();

						tmap.put(startWord, tmap.get(startWord) - 1);

						wordsLength--;

					}

					if (wordsLength == words.length) {

						list.add(StartIndex);

						String startWord = s.substring(StartIndex,StartIndex + words[0].length());

						tmap.put(startWord, tmap.get(startWord) - 1);

						wordsLength--;

						StartIndex += words[0].length();

					}

				}

				else {

					tmap.clear();

					wordsLength = 0;

					StartIndex = j + words[0].length();

				}

			}

		}

		return list;

	}

巴特西

Java for LeetCode 030 Substring with Concatenation of All Words【HARD】

最新文章

热门文章