1408. String Matching in an Array

[Problem]

Array String String Matching

---

Intuition

• This can be achieved using either a brute force approach or the more efficient KMP algorithm for substring matching.

• Although brute force will work in the question as the constraints are small, we would discuss both the approaches here.

    Constraints:
    1 <= words.length <= 100
    1 <= words[i].length <= 30
  

Resources

Before attempting this problem, consider reviewing MY TAKE ON THE KMP ALGORITHM for a clear explanation of the KMP algorithm approach.

• Additional resources to learn about the KMP Algorithm:
  • KMP Algorithm by Abdul Bari
  • KMP Algorithm for Pattern Searching GeeksForGeeks
  • Leetcode Discuss
• Few questions to practice KMP algorithm are:
  • 28. Find the Index of the First Occurrence in a String
  • 686. Repeated String Match
  • 214. Shortest Palindrome

Approach 1: Brute Force

• Compare each string with all other strings in the array.
• Check if one string is a substring of another using Java’s .contains() method.
• Add the substring to the result list if not already present.

Complexity Analysis

• Time Complexity: O(n^2 * m)
  • n: Number of strings in the array.
  • m: Average length of the strings.
• Space Complexity: O(k)
  • k: Space used to store the result list.

---

Approach 2: KMP Algorithm

• For each string, check if it is a substring of another string using the precomputed LPS (Longest Prefix Suffix) array.

• Avoid duplicates by checking if the substring is already in the result list.

• Time Complexity: O(n^2 + n * m)
  • n^2: Traversal of the string pairs.
  • n * m: KMP substring matching.
• Space Complexity: O(k + m)
  • k: Space used to store the result list.
  • m: Space used for the LPS array.

Code

class Solution {
    public List<String> stringMatching(String[] words) {
        // Brute force (uncomment for use)
        // return bruteForce(words);

        // KMP algorithm
        int n = words.length;
        List<String> res = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            String strI = words[i];

            for (int j = 0; j < n; j++) {
                if (i != j) {
                    String strJ = words[j];

                    // Check if strI is a substring of strJ using KMP
                    if (!res.contains(strI) && isSubstringKMP(strI, strJ)) {
                        res.add(strI);
                    }
                }
            }
        }

        return res;
    }

    // KMP Algorithm for substring matching
    public boolean isSubstringKMP(String pat, String text) {
        int patLen = pat.length();
        int textLen = text.length();
        
        if (patLen > textLen) {
            return false;
        }

        int[] lps = new int[patLen];
        computeLPS(pat, lps);

        int i = 0; // text pointer
        int j = 0; // pattern pointer

        while (i < textLen) {
            if (text.charAt(i) == pat.charAt(j)) {
                i++;
                j++;

                if (j == patLen) {
                    return true; // Pattern found
                }
            } else {
                if (j == 0) {
                    i++;
                } else {
                    j = lps[j - 1];
                }
            }
        }
        return false;
    }

    // Compute the LPS array for KMP
    public void computeLPS(String pat, int[] lps) {
        int len = 0;
        int i = 1;
        lps[0] = 0;

        while (i < pat.length()) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len == 0) {
                    lps[i] = 0;
                    i++;
                } else {
                    len = lps[len - 1];
                }
            }
        }
    }

    // Brute Force approach
    public List<String> bruteForce(String[] words) {
        int n = words.length;
        List<String> res = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String strI = words[i];

            for (int j = 0; j < n; j++) {
                if (i != j) {
                    String strJ = words[j];
                    if (strI.contains(strJ) && !res.contains(strJ)) {
                        res.add(strJ);
                    }
                }
            }
        }
        return res;
    }
}