Check if a string is substring of another.

Check if a string is substring of another (LeetCode 28. Implement strStr())

---

We will see two approach to check whether string is substring of another.

1. Naive approach:
Iterate through String 1 and for each index, check if there is a match found for other string.
Time complexity: O(str1 * str2)

2. Optimized Approach: Knuth Morris Pratt algorithm(KMP)
Time complexity: O(str1 + str2)

Algorithm - Naive approach

---

In this approach, we will iterate through the length of first string str1 and for each index of the string, we will compare all the characters of other string str2.
If the match is found return true, 
if not, continue the search starting from next index of str1.

KMP Algorithm: Awesome explanation - https://www.youtube.com/watch?v=GTJr8OvyEVQ

Check if a string is substring of another

---

package com.javabypatel.string;

public class CheckStringIsSubstring {
    public static void main(String[] args) {
        String str1 = "javabypatel";
        String str2 = "abyp";

        boolean result = checkIfStringIsSubstring(str1, str2);
        System.out.println(result);

        result = checkIfStringIsSubstringUsingKMPAlgorithm(str1.toCharArray(), str2.toCharArray());
        System.out.println(result);
    }

    //Naive approach: Time complexity: O(str1 * str2)
    private static boolean checkIfStringIsSubstring(String str1, String str2) {
        if (str2.length() > str1.length())
            return false;

        for (int i = 0; i <= str1.length() - str2.length(); i++) {
            int tempi = i;
            for (int j = 0; j < str2.length(); j++) {
                if (str1.charAt(tempi) == str2.charAt(j)) {
                    tempi += 1;
                } else {
                    break;
                }
            }
            // if gap between i and tempi is equal to substring length, then there is match found till last character.
            if (tempi - i == str2.length()) {
                return true;
            }
        }
        return false;
    }

    /**
     * KMP algorithm of pattern matching.
     * Optimized approach: Time complexity: O(text + pattern)
     */
    public static boolean checkIfStringIsSubstringUsingKMPAlgorithm(char[] text, char[] pattern) {

        int matchedPrefixSuffixArray[] = createPrefixSuffixMatchedCountArray(pattern);
        int i = 0;
        int j = 0;
        while (i < text.length && j < pattern.length) {
            if (text[i] == pattern[j]) {
                i++;
                j++;
            } else {
                if (j != 0) {
                    j = matchedPrefixSuffixArray[j - 1];
                } else {
                    i++;
                }
            }
        }
        if (j == pattern.length) {
            return true;
        }
        return false;
    }

    /**
     * Compute temporary array to maintain size of suffix which is same as prefix
     * Time/space complexity is O(size of pattern)
     */
    private static int[] createPrefixSuffixMatchedCountArray(char[] pattern) {
        int[] matchedPrefixSuffixArray = new int[pattern.length];
        int index = 0;
        for (int i = 1; i < pattern.length; ) {
            if (pattern[i] == pattern[index]) {
                matchedPrefixSuffixArray[i] = index + 1;
                index++;
                i++;
            } else {
                if (index != 0) {
                    index = matchedPrefixSuffixArray[index - 1];
                } else {
                    matchedPrefixSuffixArray[i] = 0;
                    i++;
                }
            }
        }
        return matchedPrefixSuffixArray;
    }
}

You may also like to see

---

Level Order Traversal of Binary Tree.

Advanced Multithreading Interview Question-Answer

Traverse a Binary Tree in Level Order Traversal

Serialize and Deserialize a Binary Tree

Find diameter of Binary Tree

How Much Water Can a Bar Graph with different heights can Hold

Interview Question-Answer on Java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.