Practice Projects

String Matching in an Array

Problem Statement

Aapke paas ek array of strings hai, jise ‘words’ kaha gaya hai. Aapko us array mein se sabhi strings return karni hai jo kisi aur string ka substring (ek chote tukde ka part) hain. Aap answer kisi bhi order mein return kar sakte hain.

Ek substring ek continuous sequence of characters hota hai jo kisi string ke andar hota hai.

Example 1: Input: words = [“mass”,”as”,”hero”,”superhero”] Output: [“as”,”hero”] Explanation: “as” “mass” ka substring hai aur “hero” “superhero” ka substring hai. [“hero”,”as”] bhi ek valid order hai.

Example 2: Input: words = [“leetcode”,”et”,”code”] Output: [“et”,”code”] Explanation: “et” aur “code” “leetcode” ke substrings hain.

Example 3: Input: words = [“blue”,”green”,”bu”] Output: [] Explanation: Koi bhi string kisi bhi dusri string ka substring nahi hai.

Constraints:

  • words ka length 1 se 100 tak ho sakta hai.

  • Har ek word ka length 1 se 30 tak ho sakta hai.

  • words ki strings mein sirf lowercase English letters hote hain.

  • Sabhi strings unique hain.

Practice Projects

String Matching in an Array

Main idea yeh hai ki humein har word ko baki sabhi words ke against check karna hai taaki yeh pata chale ki kya koi word kisi dusre word ke andar substring ki tarah appear hota hai. Humein har word ko dusre sabhi words ke sath compare karna hai, apne aap se nahi.Iska matlab yeh hai ki hum ek word uthayenge (let's call it word1), aur usko baki sabhi words ke sath check karenge (let's call these word2, word3, etc.). Agar word1 inme se kisi ke andar substring ki tarah milta hai, to hum usko result mein add karenge.Simple baasha mein, har word ke sath milan karna hai aur agar usme chhupa hua milta hai to list mein daalna hai.

Intuition

Iterate through each word: Sabse pehle, hum array ke har ek word ke upar iterate karenge.Compare with all other words: Har word ke liye, usko array ke baaki sabhi words ke saath compare karenge (sirf uss word ko chod kar jo humne pehle se select kara hai).Check substring: Agar current word kisi dusre word mein substring ke roop mein milta hai, to usko result array mein add karenge.Use break: Jaise hi current word kisi dusre word mein mil jaye (aur add ho jaye result array mein), break ka use karke duplicate addition se bacha sakte hain.

Approach
Time Complexity:

Time complexity hai: O(n^2 * k)

  • n, number of words ka signify karta hai.

  • k, average word length ka signify karta hai.

Matlab, har word ko baaki sabhi words ke sath compare karna hai. Yeh quadratic operation O(n * n) yaani O(n^2) hota hai. Aur kyonki har comparison (substring check) mein k operations involve hote hain (k word length ka average hai), isliye total complexity O(n^2 * k) hoti hai.

Space Complexity:

Space complexity hai: O(m)

  • m, matching substrings ka number hai.

Yeh kehta hai ki hume result ko store karne ke liye space chahiye, jisme m substrings hain jo match kar rahe hain.

Kyonki hamari algorithm additional data structures ya auxiliary space use nahi kar rahi, isliye space complexity primarily matching substrings ka number O(m) hoti hai.

Example ko lekar, agar n = 4 hai aur k = 5 hai, to time complexity hogi O(4^2 * 5) = O(80) aur space complexity O(m), jaha m matching substrings ka number hai.

Solution

				
					class Solution {
    // Function jo humare substring matches return karega
    stringMatching(words) {
        let result = []; // Result array jisme substrings store honge
        let n = words.length; // Words array ka length store kar rahe hain

        // Har word ke sath iterate karenge
        for(let i = 0; i < n; i++) {
            // Compare karenge current word ko baaki sabhi words ke sath
            for(let j = 0; j < n; j++) {
                // Agar word[i] word[j] mein substring ke roop mein hai aur i j ke barabar nahi hai
                if(i !== j && words[j].includes(words[i])) {
                    result.push(words[i]); // Current word ko result array mein add karenge
                    break; // Break karenge, taka duplicate na mile result mein
                }
            }
        }

        return result; // Result array return karenge
    }
}

      • Sabse pehle, humne ek empty array result banaya jisme hum matching substrings ko store karenge.

      • n variable mein words array ka length store kar rahe hain.

      • Uske baad, hum ek for loop chalate hain har word ke liye, jisse hum index i ko represent karte hain.

      • Phir ek nested for loop chalate hain, jisme hum current word ko baaki sabhi words ke sath compare karte hain, j index ka use karke.

      • if condition check karti hai ki kya word[i] kisi aur word[j] ka substring hai aur ensure karti hai ki i aur j ek dusre ke equal na ho.

      • Agar condition true hoti hai, to hum current word ko result array mein add karte hain aur loop ko break kar dete hain taaki duplicated addition na ho.

      • Last mein, result array return karte hain.

      • Overall, humara code har word ko baaki sabhi words ke sath compare karta hai talaashi ke liye ki kya koi word kisi aur word ke andar substring ke roop mein hai. Agar aisa hota hai, to hum usko result array mein store kar lete hain aur loop se break ho jate hain.

Solution

				
					class Solution {
public:
    // Function jo substring matches return karega
    vector<string> stringMatching(vector<string>& words) {
        vector<string> result; // Result array jisme substrings store honge
        int n = words.size(); // Words array ka length store kar rahe hain
        
        // Har word ke sath iterate karenge
        for(int i = 0; i < n; i++) {
            // Compare karenge current word ko baaki sabhi words ke sath
            for(int j = 0; j < n; j++) {
                // Agar i aur j barabar nahi hain aur word[i] word[j] mein substring ke roop mein hai
                if(i != j && words[j].find(words[i]) != string::npos) {
                    result.push_back(words[i]); // Result array mein current word ko add kar rahe hain
                    break; // Break kar rahe hain to avoid duplicates
                }
            }
        }
        
        return result; // Result array return kar rahe hain
    }
};

    • Humne pehle ek class Solution banai aur public section mein ek function stringMatching likha jo vector of strings words ko input lega aur vector of strings result ko return karega.

    • result naam se ek empty vector create kiya jisme matching substrings ko store karenge.

    • n variable mein words array ka length store kar liya.

    • for loop use karke outer loop lagaya hai, jo i ke through har word pe iteration karta hai.

    • Ek nested for loop lagaya jo j ke through current word ko baaki sabhi words ke saath compare karta hai.

      • if condition check kar rahi hai ki i aur j barabar nahi hain aur words[i] words[j] mein substring ke roop mein milta hai.

      • Agar condition true hoti hai, to words[i] ko result vector mein add kar dete hain aur break use karte hain taki duplicate addition na ho.

      • Last mein, result vector return kiya jata hai jisme matching substrings hain.

      Code ka logic hai simple: sabhi words ko ek dusre ke saath compare karke check karte hain ki kya koi word kisi dusre word ka substring hai. Matching words ko result vector mein add karke return karte hain.