CareerCup

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

SOLUTION:

boolean find(String s1, String s2) {
        if(s1.isEmpty()) return false;
        int l1 = s1.length(), l2 = s2.length();
        if(l1 >= l2) {
            return kmp(s1 + s1, s2); //find if s2 is a substring of s1 + s1
        } else {
            for(int i = 0; i < l1; i++) {
                if(match(s1, i, s2)) return true; //find if s2 is made of multiple rotated s1
            }
        }
        return false;
    }

    boolean match(String s1, int j, String s2) {
        int idx = 0;
        while(idx < s2.length()) {
            if(s2.charAt(idx) != s1.charAt(j)) {
                return false;
            }
            idx++;
            j = j % s1.length();
        }
        return true;
    }

    boolean kmp(String haystack, String needle) {

        if (haystack.length() < needle.length()) {

            String t = haystack;

            haystack = needle;

            needle = t;

        }

        int[] table = new int[needle.length() + 1];

        for (int i = 1; i < needle.length(); i++) {

            int j = table[i];

            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {

                j = table[j];

            }

            table[i + 1] = (needle.charAt(i) == needle.charAt(j)) ? j + 1 : 0;

        }


        haystack += haystack;

        int j = 0;

        for (int i = 0; i < haystack.length(); i++) {

            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) {

                j = table[j];

            }

            if (needle.charAt(j) == haystack.charAt(i)) {

                j++;

            }

            if (j == needle.length()) {

                return true;

            }

        }

        return false;
    
}

The Goal is to find the value of n here

private void isS2SubstringOfS3(String s1, String s2){
	int n = (int)Math.ceil(((double)s2.length() -1) % s1.length()) + 1;
	String s3 = formString(s1, n);
	return s3.contains(s2); // use KMP String match here
}

private String formString(String s1, int n){
	StringBuilder sb = new StringBuilder();
	while(n > 0){
		sb.append(s1);
		--n;
	}
	return sb.toString();
}

def isSubstringOfRepetition(s1: String, s2: String): Boolean =
    if (s1.contains(s2)) {
      true
    } else {
      if (s1.length > s2.length * 4) {
        false
      } else {
        isSubstringOfRepetition(s1 + s1, s2)
      }
    }

def isSubstringOfRepetition(s1: String, s2: String): Boolean =
    if (s1.contains(s2)) {
      true
    } else {
      if (s1.length > s2.length * 4) {
        false
      } else {
        isSubstringOfRepetition(s1 + s1, s2)
      }
    }

public class stringProcess{
	public static void main(String[] args){
		String s1 = "aabc";
		String s2 = "caabcaa";
		String s3= "";
		//you have to find the value of n;
		
		for(int i=0;i<s2.length();i++){
			s3 = s3+s1;
			if(s3.indexOf(s2) > 0){
			   System.out.println("true and n = "+i+1);
			   break;
			   }
		}
		
	}
}

Solution in JS

function run() {    
    let s1 = 'aabc';
    let s2 = 'bcaab';
    let maxCycle = 4;
    let matchStarted = false;
    for (i = 0; i < s2.length; i++) {
        j = 0;
        while (j < s1.length) {
            if (s1[j] == s2[i]) {
                j++; i++;
                matchStarted = true;
            } else {
                if(matchStarted){
                    i=0;
                    matchStarted = false;            
                }
                j++;
            }
            if (i == s2.length) {
                console.log('Matching !');
                return;
            }
            if (j == s1.length) {
                j = 0;
                if (maxCycle < 0) {
                    console.log('its too much - give up !');
                    return;
                }
                maxCycle--;
            }
        }
    }
}

a not wonky solution. O(L1 * L2) in the worst possible case (s1 = "aaaab", s2 = "ab").

static boolean isSub(String s1, String s2) {
        if (s2.isEmpty()) return true;

        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                int s1I = (i + j) % s1.length();

                if (s1.charAt(s1I) != s2.charAt(j)) {
                    break;
                } else if (j == s2.length() - 1) {
                    return true;
                }
            }
        }

        return false;
    }