सभी शब्दों के सामंजस्य के साथ पदार्थ  


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना डीई शॉ
hashing तार दो सूचक

सभी शब्दों की समस्या के समाधान के साथ, हमने एक दिया है स्ट्रिंग s और एक सूची में कई शब्द समान लंबाई के होते हैं। किसी भी क्रम में सूची के सभी शब्दों के संयोजन का परिणाम हो सकने वाले सबस्ट्रिंग के शुरुआती सूचकांक को प्रिंट करें।

  

सभी शब्दों के सामंजस्य के साथ प्रतिस्थापन के लिए स्पष्टीकरण  

स्ट्रिंग को s = "capcodthecodcap" और दी गई सूची L = ["cap", "cod"] दें

दी गई सूची के सभी शब्दों को समाप्‍त करें। दिए गए सूची के सभी शब्दों को समवर्ती के सभी संभावित संयोजन हैं -

  • कैपकोड
  • कूट-कूट कर भरा हुआ

अब, दिए गए स्ट्रिंग में संघनित तारों के शुरुआती सूचकांक को खोजें।

दिए गए स्ट्रिंग में "कैपकोड" के विकल्प का इंडेक्स शुरू करनाकैपकोडthecodcap ”0 है।

दिए गए स्ट्रिंग "capcodthe" में "कोडक" के विकल्प का इंडेक्स शुरू करनाकूट-कूट कर भरा हुआ”9 है।

इसलिए, आउटपुट 0 और 9 होगा।

उदाहरण  

इनपुट: 

s = "capcodthecodcap"

एल = ["कैप", "कॉड"]

आउटपुट:

0 9

इनपुट: 

s = "हीथेजेनना"

एल = ["हे", ""]

आउटपुट:

कलन विधि  

  1. लंबाई n के एक स्ट्रिंग s को प्रारंभ करें और दिए गए स्ट्रिंग के समान लंबाई के शब्दों की एक सूची।
  2. एक मानचित्र और एक अस्थायी मानचित्र को प्रारंभ करें।
  3. दी गई सूची के सभी शब्दों के समतुल्य के बराबर लंबाई के सभी संभावित पदार्थों के माध्यम से आफ्टेट।
  4. सभी संभावित सबस्ट्रिंग का उपयोग करके नए मानचित्र को पुराने मानचित्र के साथ लिंक करें।
  5. जाँच करें कि क्या सबस्ट्रिंग के शब्द नए नक्शे में मौजूद हैं, गिनती को 1 से घटाएँ, अन्यथा लूप को तोड़ दें।
  6. नए नक्शे के माध्यम से आगे बढ़ें और जांचें कि क्या सभी शब्दों की गिनती 0 से कम है, सूची / सरणी रेस वापस करें।
  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

जावा प्रोग्राम सभी शब्दों के संयोजन के साथ विकल्प खोजने के लिए  

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 कुल लंबाई है जब सभी सूची शब्दों को संक्षिप्त कर दिया गया है)

संदर्भ