[LeetCode] 30. Substring with Concatenation of All Words

轉自 LeetCode

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

<Solution>

這題的題意是，在 words 裡面的字串組成的 string (順序不一定)，是 s 裡面的一個 sub-string

例如 foobar、barfoo 是不是有在 s 裡面

有的話，把 substring 的開頭字元的 index 回傳

解題想法如下(參考資料)

• 先用一個 hash map 把 words 裡面的字存起來，key 是 string，value 是此 string 在 words 裡面出現的次數

• 因為題目有說在 words 裡面的 string 長度都是一樣的，所以可以根據其長度來抓取 substring

• 每個 substring 都先去步驟一的 hash map 裡面查是否存在，不存在就直接 break，代表此 substring 是不在 words 裡的

• 如果存在，那再用一個 hash map 存起來，key 就是 substring，value 是此 substring 出現的次數。因為題目有說，每個 words 裡面的 string 只能用一次，所以如果 substring 出現次數比 words 裡的還多，那也是不符合

code 如下

c++

	class Solution {
	public:
	vector<int> findSubstring(string s, vector<string>& words) {
	vector<int> ans;
	if(s.empty() || words.empty()) {
	return ans;
	}
	const int wordCnt = words.size();
	const int wordLen = words[0].length();
	const int strLen = s.length();
	const int subStrLen = wordLen * wordCnt;
	//> create hash map of words
	unordered_map<string, int> wordsHashMap;
	for(auto w : words) {
	wordsHashMap[w]++;
	}
	//> find index of substring
	for(int i = 0; i <= strLen - subStrLen; i++) {
	unordered_map<string, int> matchHashMap;
	int j;
	for(j = 0; j < wordCnt; j++) {
	string tmpStr = s.substr(i + j * wordLen, wordLen);
	//> tmpStr not in words
	if(wordsHashMap.find(tmpStr) == wordsHashMap.end()) {
	break;
	}
	matchHashMap[tmpStr]++;
	//> if tmpStr is used more than once
	if(matchHashMap[tmpStr] > wordsHashMap[tmpStr]) {
	break;
	}
	}
	if(j == wordCnt) {
	ans.push_back(i);
	}
	}
	return ans;
	}
	};

view raw substringWithConcatenationOfAllWords.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun findSubstring(s: String, words: Array<String>): List<Int> {
	val wordMap = mutableMapOf<String,Int>()
	for(s in words) {
	wordMap[s] = wordMap[s]?.let { it + 1 } ?: 1
	}
	var ans = mutableListOf<Int>()
	val wordLen = words[0].length
	val upBound = s.length - (wordLen * words.size)
	for(i in 0..upBound) {
	var j = 0
	val matchMap = mutableMapOf<String,Int>()
	while(j < words.size) {
	val str = s.substring(i + j * wordLen, i + j * wordLen + wordLen)
	if(!wordMap.containsKey(str)) {
	break
	}
	matchMap[str] = matchMap[str]?.let { it + 1 } ?: 1
	if(matchMap[str]!! > wordMap[str]!!) {
	break
	}
	++j
	}
	if (j == words.size) {
	ans.add(i)
	}
	}
	return ans
	}
	}

view raw substring_with_concatenation_of_all_words.kt hosted with ❤ by GitHub