帶有所有單詞串聯的子字符串


難度級別
經常問 亞馬遜
哈希 兩指針

在所有單詞串聯問題的子字符串中,我們給出了一個 s和一個列表由許多相同長度的詞組成。 打印子字符串的起始索引,該索引可以是列表中所有單詞以任意順序串聯的結果。

帶有所有單詞串聯的子字符串的解釋

假設字符串s =“ capcodthecodcap”,給定列表L = [“ cap”,“ cod”]

連接給定列表的所有單詞。 連接給定列表的所有單詞的所有可能組合為–

  • 卡普科德
  • 鱈魚

現在,在給定字符串中搜索串聯字符串的起始索引。

給定字符串“卡普科德thecodcap”為0。

給定字符串“ capcodthe”中子字符串“ codcap”的起始索引鱈魚”是9。

因此,輸出將為0和9。

輸入: 

s =“ capcodthecodcap”

L = [“蓋帽”,“鱈魚”]

輸出:

0 9

輸入: 

s =“ heythejenna”

L = [“嘿”,“該”]

輸出:

0

算法

  1. 初始化長度為n的字符串s和與給定字符串長度相同的單詞列表。
  2. 初始化地圖和臨時地圖。
  3. 後跟遍歷所有長度等於給定列表的所有單詞的串聯的可能子字符串。
  4. 使用所有可能的子字符串將新地圖與舊地圖鏈接。
  5. 檢查新映射中是否存在子字符串的單詞,將計數減1,否則中斷循環。
  6. 遍歷新映射並檢查所有單詞的計數是否小於0,然後返回列表/數組res。
  7. 遍歷返回的列表/數組,並打印存儲在其中的所有值。

C ++程序查找所有單詞串聯在一起的子字符串

#include <bits/stdc++.h> 
using namespace std; 
  
vector<int> Substring(string s, const vector<string>& L){ 
  
    int size = L[0].size(); 
  
    int count = L.size(); 
  
    int length = size * count; 
  
    vector<int> res; 
  
    if(length>s.size()) 
        return res; 
  
    unordered_map<string, int> hash_map; 
  
    for(int i=0; i<count; i++)  
        hash_map[L[i]]++;     
  
    for(int i=0; i<=s.size()-length; i++) { 
        unordered_map<string, int> temp_hash_map(hash_map); 
  
        int j = i,c=count; 
  
        while(j<i+length){ 
  
            string word = s.substr(j, size); 
  
  
            if(hash_map.find(word) == hash_map.end()||temp_hash_map[word]==0) 
                break; 
  
            else{ 
                temp_hash_map[word]--;
                c--;
            }  
            j += size; 
        } 
       
        if(c == 0) 
            res.push_back(i); 
    } 
  
    return res; 
} 
  
int main(){ 
    string s = "capcodthecodcap"; 
    vector<string> L = { "cap", "cod" }; 
    vector<int> indices = Substring(s, L); 
    for(int i=0; i<indices.size(); i++) 
        cout<<indices[i]<<" "; 
    return 0; 
}
0 9

Java程序查找所有單詞串聯在一起的子字符串

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashMap; 
import java.util.List;

class sub{
    
    public static ArrayList<Integer>Substring(String s, final List<String> L){ 
  
        int size = L.get(0).length(); 
         
        int count = L.size(); 
  
        int length = size * count; 
  
        ArrayList<Integer> res = new ArrayList<Integer>(); 
        int n = s.length(); 
          
        if(length > n){ 
            return res; 
        } 
  
        HashMap<String, Integer> hashMap = new HashMap<String, Integer>(); 
  
        for(String word : L){ 
            hashMap.put(word, hashMap.getOrDefault(word, 0) + 1); 
        } 
  
          
        for(int i=0; i<=n-length; i++){ 
            HashMap<String, Integer> tempMap = (HashMap<String, Integer>) hashMap.clone(); 
            int j = i, c = count; 
              
            while(j<i+length){ 
                String word = s.substring(j, j+size); 
              
                if(!hashMap.containsKey(word) || tempMap.get(word) == 0){ 
                    break; 
                }  
                  
                else{ 
                    tempMap.put(word, tempMap.get(word) - 1); 
                    c--; 
                } 
                j += size; 
            } 
              
            if(c == 0){ 
                res.add(i); 
            } 
  
        } 
        return res; 
    } 
  
    public static void main(String[] args){ 
        String s = "capcodthecodcap"; 
        ArrayList<String> L = new ArrayList<>(Arrays.asList("cap", "cod")); 
        ArrayList<Integer> indices = Substring(s, L); 
        for(Integer i : indices){
            System.out.print(i+" "); 
        } 
    }
}
0 9

時間複雜度: O(nk)* k(n是字符串的長度,k是所有列表詞連接後的總長度)

參考