iT邦幫忙

2025 iThome 鐵人賽

0
自我挑戰組

leetcode系列 第 30

leetcode 30. Substring with Concatenation of All Words

  • 分享至 

  • xImage
  •  

題目:
You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.
Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.
給定一個字串s和一個字串數組words。所有字串的長度words相同。

連接字串是恰好包含任何連接排列的所有字串的字串words。

例如,如果words = ["ab","cd","ef"],則"abcdef","abefcd","cdabef","cdefab","efabcd"和"efcdab"都是連接字串。"acdbef"不是連接字串,因為它不是 的任何排列的連接words。
傳回中所有連接子字串的起始索引數組。您可以按任意順序s返回答案。
https://ithelp.ithome.com.tw/upload/images/20251020/201693404VP57OjAYv.png
https://ithelp.ithome.com.tw/upload/images/20251020/20169340OFGu85TblH.png
解題思路(滑動視窗 + 雜湊表 HashMap)

觀察特性

每個 word 長度一樣 → 設為 wordLen。

words 數量固定 → 串接長度為 totalLen = wordLen * words.length。

用 HashMap 記錄單字出現次數

Map<String, Integer> wordCount = new HashMap<>();

滑動視窗

用 i 遍歷起始點(從 0 到 wordLen-1)。

每次以 wordLen 為步長切分字串。

用另一個 HashMap seen 記錄當前視窗出現的單字數。

若出現不在 words 裡的單字 → 清空視窗。

若單字超出允許次數 → 收縮左邊界。

當視窗長度剛好等於 totalLen 時 → 記錄起始索引。


上一篇
LeetCode 第 29 題:Divide Two Integers
系列文
leetcode30
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言