Count Prefix and Suffix Pairs I
Problem Statement
Aapko ek 0-indexed string array words di gayi hai.
Ek boolean function isPrefixAndSuffix define karte hain jo do strings leta hai, str1 aur str2:
isPrefixAndSuffix(str1, str2) true return karta hai agar str1 prefix bhi ho aur suffix bhi ho str2 ka, aur false otherwise. Maan lijiye, isPrefixAndSuffix(“aba”, “ababa”) isliye true hai kyunki “aba” “ababa” ka prefix bhi hai aur suffix bhi, lekin isPrefixAndSuffix(“abc”, “abcd”) false hai.
Aapko ek integer return karna hai jo denote karein number of index pairs (i, j) jisme i < j, aur isPrefixAndSuffix(words[i], words[j]) true ho.
Example 1:
Input: words = [“a”,”aba”,”ababa”,”aa”] Output: 4
Explanation: Is example mein count kiye gaye index pairs ye hain:
i = 0 aur j = 1 kyunki isPrefixAndSuffix(“a”, “aba”) true hai.
i = 0 aur j = 2 kyunki isPrefixAndSuffix(“a”, “ababa”) true hai.
i = 0 aur j = 3 kyunki isPrefixAndSuffix(“a”, “aa”) true hai.
i = 1 aur j = 2 kyunki isPrefixAndSuffix(“aba”, “ababa”) true hai.
Isliye, answer 4 hai.
Example 2:
Input: words = [“pa”,”papa”,”ma”,”mama”] Output: 2
Explanation: Is example mein count kiye gaye index pairs ye hain:
i = 0 aur j = 1 kyunki isPrefixAndSuffix(“pa”, “papa”) true hai.
i = 2 aur j = 3 kyunki isPrefixAndSuffix(“ma”, “mama”) true hai.
Isliye, answer 2 hai.
Example 3:
Input: words = [“abab”,”ab”] Output: 0
Explanation: Is example mein valid index pair i = 0 aur j = 1 hai, lekin isPrefixAndSuffix(“abab”, “ab”) false hai.
Isliye, answer 0 hai.
Constraints:
1 <= <= 50
1 <= words[i].length <= 10
words[i] mein sirf chhoti English letters hain.
Count Prefix and Suffix Pairs I
Prefix aur Suffix Check:
Pata karna hai ki pehla string, str1, dusre string, str2 ka prefix aur suffix dono ho sakta hai ya nahi. Matlab str1 ko str2 ke beginning aur end pe match karwana hoga.
Socho str1 ek chhoti piece hai aur str2 ek badi wali piece.
Example ke liye, agar str1 "ab" hai, toh "ab" ko str2 ka start (prefix) aur end (suffix) dono pe match karwana hai.
Compare Extracted Parts with Original String:
Str2 ke start se str1 ki length ka segment nikaalo aur dekho kya vo str1 se match ho raha hai.
Similarly, str2 ke end se bhi wahi length ka segment nikalke dekho kya vo str1 se match ho raha hai.
Example dekhte hain:
Agar str1 "ab" aur str2 "abab" ho:
Prefix: "ab" kya "abab" ke beginning mein hai? Haan. ✔️
Suffix: "ab" kya "abab" ke end mein hai? Haan. ✔️
To, isPrefixAndSuffix("ab", "abab") true return karega.
Count Valid Pairs:
Words array mein har pair (i, j) ke liye jaha i < j hai, check karo ki isPrefixAndSuffix(words[i], words[j]) true hai ya nahi. Aise pairs ko count karna hai.
Example Illustration: Maan lo words array: ["a", "aba", "ababa", "aa"].
Pair (i = 0, j = 1):
Prefix: "a", "aba" ke beginning mein hai
Suffix: "a", "aba" ke end mein bhi hai ✔️
Pair (i = 0, j = 2):
Prefix: "a", "ababa" ke beginning mein hai
Suffix: "a", "ababa" ke end mein bhi hai
Pair (i = 1, j = 2):
Prefix: "aba", "ababa" ke beginning mein hai
Suffix: "aba", "ababa" ke end mein bhi hai
Aur aise hi aur pairs check karte hain.
Jitne pairs ke liye ye prefix aur suffix conditions match hoti hain, unko count karte hain aur result mil jata hai.
Isse systematically har pair ko compare karte hue words array mein valid (i, j) pairs count kiye ja sakte hain.
Har Pair (i, j) jahan i < j ho:
Pehla string s1 ko words[i] se nikaalo.
Dusra string s2 ko words[j] se nikaalo.
Length Check:
Agar s2 ki length s1 ki length se choti hai, toh seedha skip kar do. (Kyunki yeh waise bhi possible nahi hoga match hona.)
Prefix aur Suffix Extract karo:
S2 ke starting se s1 ki length ke barabar ka prefix nikaalo.
S2 ke ending se s1 ki length ke barabar ka suffix nikaalo.
Matching Check:
Agar dono prefix aur suffix s1 se match karte hain, toh count increment karo.
Example Illustration: Maan lo words array: ["a", "aba", "ababa", "aa"].
Pair (i = 0, j = 1):
s1 = "a"
s2 = "aba"
Length check pass ho gaya kyunki "aba" > "a".
Prefix of length 1: "a"
Suffix of length 1: "a"
Both match "a", so count increase ho gaya.
Pair (i = 1, j = 2):
s1 = "aba"
s2 = "ababa"
Length check pass ho gaya kyunki "ababa" > "aba".
Prefix of length 3: "aba"
Suffix of length 3: "aba"
Time Complexity:
Time complexity O(n^2 * m) hoti hai, matlab kehne ka yeh hai ki:
n: Yeh words array ka length hai.
n^2: Hum har pair (i, j) ko check kar rahe hain jahan i < j. Iska matlab hai ki har possible pair ko compare karna hai, jo n^2 operations ke barabar hai.
m: Yeh strings ka average length hai. Har pair ke liye, hume strings ko compare karna hota hai, jo m ke barabar operations leti hai.
Jab hum yeh steps follow karte hain, toh overall time complexity O(n^2 * m) banti hai.
Space Complexity:
Space complexity O(1) hoti hai, matlab:
Hum fixed extra space use kar rahe hain, jo string comparisons ke liye hai.
Iska matlab hai ki hum sirf kuch variables use kar rahe hain, aur koi additional arrays ya complex structures nahi ban rahe.
O(1).
Solution
var countPrefixSuffixPairs = function(words) {
let n = words.length; // Words array ka length nikal rahe hain
let ans = 0; // Answer ko initial value 0 de rahe hain
for(let i = 0; i < n; i++) { // Har word ke liye loop
let s1 = words[i]; // Pehla word s1
for(let j = i + 1; j < n; j++) { // Dusra word ke liye loop j i+1 se start
let s2 = words[j]; // Dusra word s2
if(s2.length < s1.length) continue; // Agar s2 ka length s1 se chota hai, skip kar do
let pre = s2.slice(0, s1.length); // S2 ka prefix nikal rahe hain
let suf = s2.slice(-s1.length); // S2 ka suffix nikal rahe hain
if(pre === s1 && suf === s1) { // Agar prefix aur suffix dono match karte hain s1 se
ans++; // Answer increment kar do
}
}
}
return ans; // Answer return karo
};
Function Initialization: Humne countPrefixSuffixPairs ek function banaya jo words array ko input leta hai aur pairs count karta hai jahan prefix aur suffix match hota hai.
Length Calculation: n variable mein words array ka length store kar rahe hain, aur ans variable ko 0 se initialize kiya hai jisme count store hoga.
Outer Loop: Pehli loop har word ko iterate karti hai. s1 variable mein current word ko store karte hain.
Inner Loop: Dusri loop i ke baad ke har word ko iterate karti hai. s2 variable mein current word ko store karte hain jo s1 ke baad aata hai.
Length Check: Agar s2 ka length s1 se chota hai, toh skip kar dete hain (continue statement).
Prefix and Suffix Extraction: s1 ke length ke barabar ka prefix aur suffix s2 se nikalte hain. pre variable mein prefix aur suf variable mein suffix store karte hain.
Match Check: Agar pre aur suf dono s1 se match karte hain, toh ans ko increment kar dete hain.
Return Answer: Jab saari loop complete ho jaati hain, toh final ans ko return karte hain.
Solution
class Solution { // Solution class banaya hai
public:
int countPrefixSuffixPairs(vector<string>& words) { // Function jo words vector ko input leta hai
int n = words.size(); // n mein words ka size store karte hain
int ans = 0; // Answer variable ko 0 se initialize kar rahe hain
for (int i = 0; i < n; i++) { // Pehli loop: Har word ke liye iterate kar rahe hain
string s1 = words[i]; // s1 variable mein current word ko store karte hain
for (int j = i + 1; j < n; j++) { // Dusri loop: i ke baad ke har word ke liye iterate kar rahe hain
string s2 = words[j]; // s2 variable mein current word ko store karte hain jo s1 ke baad aata hai
// Agar s2 ka length s1 se chota hai, toh skip kar dete hain.
if (s2.length() < s1.length())
continue;
// s1 ke length ke barabar ka prefix aur suffix s2 se nikalte hain
string pre = s2.substr(0, s1.length());
string suf = s2.substr(s2.length() - s1.length());
// Agar prefix aur suffix dono s1 se match karte hain, ans ko increment karte hain
if (pre == s1 && suf == s1) {
ans++;
}
}
}
return ans; // Final answer return karte hain
}
};
Class Initialization: Solution class banaya hai jisme countPrefixSuffixPairs function hota hai.
Length Calculation: n variable mein words ka size store karte hain, aur ans variable ko 0 se initialize karte hain jisme count store hoga.
Outer Loop: Pehli loop har word ko iterate karti hai. s1 variable mein current word ko store karte hain.
Inner Loop: Dusri loop i ke baad ke har word ko iterate karti hai. s2 variable mein current word ko store karte hain jo s1 ke baad aata hai.
Length Check: Agar s2 ka length s1 se chota hai, toh skip kar dete hain (continue statement).
Prefix and Suffix Extraction: s1 ke length ke barabar ka prefix aur suffix s2 se nikalte hain. pre variable mein prefix aur suf variable mein suffix store karte hain.
Match Check: Agar pre aur suf dono s1 se match karte hain, toh ans ko increment kar dete hain.
Return Answer: Jab saari loop complete ho jaati hain, toh final ans ko return karte hain.
