解法一：使用递归
def find_substrings(s, words):
if not s or not words:
return []
word_length = len(words[0])
num_words = len(words)
total_length = word_length * num_words
substrings = []
def find_substrings_helper(s, words, current_string):
nonlocal substrings
if len(current_string) == total_length:
substrings.append(current_string)
return
for i in range(len(words)):
if s.startswith(words[i]):
find_substrings_helper(s[word_length:], words[:i] + words[i+1:], current_string + words[i])
find_substrings_helper(s, words, "")
return substrings解法二：使用滑动窗口
from collections import Counter
def find_substrings(s, words):
if not s or not words:
return []
word_length = len(words[0])
num_words = len(words)
total_length = word_length * num_words
substrings = []
word_counts = Counter(words)
for i in range(len(s) - total_length + 1):
substring = s[i:i+total_length]
substring_counts = Counter([substring[j:j+word_length] for j in range(0, total_length, word_length)])
if substring_counts == word_counts:
substrings.append(substring)
return substrings解法三：使用哈希表
from collections import defaultdict
def find_substrings(s, words):
if not s or not words:
return []
word_length = len(words[0])
num_words = len(words)
total_length = word_length * num_words
substrings = []
word_counts = defaultdict(lambda: 0)
for word in words:
word_counts[word] += 1
for i in range(len(s) - total_length + 1):
substring = s[i:i+total_length]
substring_counts = defaultdict(lambda: 0)
for j in range(0, total_length, word_length):
substring_counts[substring[j:j+word_length]] += 1
if substring_counts == word_counts:
substrings.append(substring)
return substrings