当前位置：首页 > news >正文

LeetCode -- Substring with Concatenation of All Words

news 来源：原创 2024/5/7 0:11:02

题目描述：
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).

题目意思是说给定1个字符串s和一个单词数组words，个数为n，每个单词的长度都是l。
扫描s，判断在l * n范围内，判断是否words中的每个单词在s [i , l*n]内只出现了一次（如果words中包含1个单词多次,其中i∈[0,Len(s) - l*n)
注意，如果words本身包含重复的单词，那么这个单词也允许在s[i, l*n]中出现相同的次数

思路：
1. 使用哈希表1 ：hash，遍历单词数组，存所有的单词以及出现的次数
2. 使用哈希表2 ：hash2，在s中逐个截取长度为l的字符串str，如果str在hash1出现，添加到hash2中，其中l=s[i, words[j] * l]
3. 每次判断hash1中的元素是否完全等于hash2

实现代码：

public class Solution {
    public IList<int> FindSubstring(string s, string[] words) {
        
   	if(string.IsNullOrWhiteSpace(s) || words == null || s.Length < words.Length * words[0].Length){
		return new List<int>();
	}
	
	
	var wLen = words[0].Length;
	var result = new List<int>();
	var len = words.Length * wLen;
		
	var hash = new Dictionary<string, int>();
	for(var i = 0;i < words.Length; i++){
		if(!hash.ContainsKey(words[i])){
			hash.Add(words[i], 1);
		}
		else{
			hash[words[i]] ++;
		}
	}
	
	var h = new Dictionary<string, int>();
	for(var i = 0; i < s.Length - len + 1; i++){
		for(var j = 0;j < words.Length; j++){
			var str = s.Substring(i + j * wLen, wLen);
			if(hash.ContainsKey(str)){
				if(!h.ContainsKey(str)){
					h.Add(str,1);
				}
				else{
					h[str] ++;
				}
			}
		}
		
		if(hash.All(x=>h.ContainsKey(x.Key) && h[x.Key] == x.Value)){
			result.Add(i);
		}
		
		var k2 = new List<string>(h.Keys);
		foreach(var k in k2){
			h[k] = 0;
		}
	}
	
	
	return result;
    }
}