Given two Lists of strings s1 and s2, you have to count the number of strings in s2 which is either a suffix or prefix of at least one string of s1.
Examples:
Input: s1 = [“cat”, “catanddog”, “lion”], s2 = [“cat”, “dog”, “rat”]
Output: 2
Explanation:
- String “cat” of s2 is a prefix of “catanddog”
- string “dog” of s2 is suffix of “catanddog”
Input: s1 = [“jrjiml”, “tchetn”, “ucrhye”, “ynayhy”, “cuhffd”, “cvgpoiu”, “znyadv”], s2 = [“jr”, “ml”, “cvgpoi”, “gpoiu”, “wnmkmluc”, “geheqe”, “uglxagyl”, “uyxdroj”]
Output: 4
Explanation: String “jr” of s2 is a prefix of “jrjiml”, “ml” of s2 is the suffix of “jrjiml”, “cvgpoi” of s2 is a prefix of “cvgpoiu” & “gpoiu” of s2 is the suffix of “cvgpoiu”
Approach: This can be solved with the following idea:
- A prefix-suffix string is a string created by joining a prefix and a suffix from the same string together. For instance, the prefix-suffix string for the string “abab” is “ab”.
- Algorithms for string matching and compression are just two examples of how the prefix-suffix string is used in computer science. One illustration is the Knuth-Morris-Pratt (KMP) algorithm for string matching, which effectively searches for a pattern inside a bigger text using the prefix-suffix characteristic.
- The prefix-suffix attribute of the pattern is used by the KMP algorithm to create a table of values. This table, sometimes referred to as the partial match table or the failure function, is used to avoid pointless comparisons when string matching is being done.
Below are the steps involved in the implementation of the code:
- Initialize an array with all values set to 0 and a size equal to the length of the pattern.
- Continue the pattern iteratively, beginning with the second character.
- Discover the longest proper prefix that also functions as a proper suffix of the substring that ends at each character.
- Insert the length of this prefix into the array at the appropriate point.
- Set the value to 0 if the correct prefix-suffix is not present.
Below is the implementation of the above code:
C++
// C++ code for the above approaach:#include <algorithm>#include <iostream>#include <vector>using namespace std;// Function to find the count of s2// strings present as suffic or prefixint prefixSuffixString(vector<string> s1, vector<string> s2){ int count = 0; for (string s : s2) { for (string t : s1) { // If found if (t.find(s) == 0 || t.rfind(s) == t.length() - s.length()) { count++; break; } } } // Return the ans return count;}// Driver codeint main(){ vector<string> s1 = { "cat", "catanddog", "lion" }; vector<string> s2 = { "cat", "dog", "rat" }; // Function call cout << prefixSuffixString(s1, s2) << endl; return 0;} |
Java
// Java code for the above approaachimport java.util.ArrayList;import java.util.List;public class GFG { // Function to find the count of s2 // strings present as suffix or prefix static int prefixSuffixString(List<String> s1, List<String> s2) { int count = 0; for (String s : s2) { for (String t : s1) { // If found if (t.startsWith(s) || t.endsWith(s)) { count++; break; } } } // Return the answer return count; } // Driver code public static void main(String[] args) { List<String> s1 = new ArrayList<>(); s1.add("cat"); s1.add("catanddog"); s1.add("lion"); List<String> s2 = new ArrayList<>(); s2.add("cat"); s2.add("dog"); s2.add("rat"); // Function call System.out.println(prefixSuffixString(s1, s2)); }}// This code is contributed by Utkarsh Kumar |
Python3
# Python code for the above approach:def prefixSuffixString(s1, s2): count = 0 for s in s2: for t in s1: if t.startswith(s) or t.endswith(s): count += 1 break return countif __name__ == "__main__": s1 = ["cat", "catanddog", "lion"] s2 = ["cat", "dog", "rat"] print(prefixSuffixString(s1, s2)) |
C#
using System;using System.Collections.Generic;class Program{ // Function to find the count of s2 // strings present as suffic or prefix static int PrefixSuffixString(List<string> s1, List<string> s2) { int count = 0; foreach (string s in s2) { foreach (string t in s1) { // If found if (t.StartsWith(s) || t.EndsWith(s)) { count++; break; } } } // Return the ans return count; } static void Main(string[] args) { // Function call List<string> s1 = new List<string> { "cat", "catanddog", "lion" }; List<string> s2 = new List<string> { "cat", "dog", "rat" }; Console.WriteLine(PrefixSuffixString(s1, s2)); }} |
Javascript
// Function to find the count of s2// strings present as suffic or prefixfunction prefixSuffixString(s1, s2) { let count = 0; for (let s of s2) { for (let t of s1) { // If found if (t.indexOf(s) === 0 || t.lastIndexOf(s) === t.length - s.length) { count++; break; } } } // Return the ans return count;} // Function calllet s1 = ["cat", "catanddog", "lion"];let s2 = ["cat", "dog", "rat"];console.log(prefixSuffixString(s1, s2)); |
Output
2
Time complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
