Interview Question
SDE-2sCountry: United States
Here's a KMP implementation:
public static boolean isIn(String str1, String str2){
char[] arr1 = str1.getChars();
char[] arr2 = str2.getChars();
//compute table for str2:
int[] t = computeTable(arr2);
int arr1Index = 0, arr2Index = 0;
while(arr1Index + arr2Index < arr1.length){
if(arr1[arr1Index + arr2Index] == arr2[arr2Index]){
arr2Index++;
if(arr2Index == arr2.length){
return true;
}
}
else{
if(t[arr2Index] > -1){
arr1Index += (arr2Index - t[arr2Index]);
arr2Index = t[arr2Index];
}
else{
arr1Index++;
arr2Index = 0;
}
}
}
return false;
}
private static int[] computeTable(char[] arr){
int[] table = new int[arr.length];
int i = 1; m = 0;
table[0] = -1;
while(i < arr.length){
if(arr[i] == arr[m]){
table[i] = m;
m++;
i++;
}
else if (m > 0){
m = t[m];
else {
table[i] = 0;
i++;
}
}
return table;
}
Objective C solution
NSString *stringOne = @"aaaaaabbb";
NSString *stringTwo = @"aaaaaabbbbbbb";
BOOL containsString = NO;
if (stringOne.length>stringTwo.length) {
//NSLog(@"Contains Substring: %d",[stringOne containsString:stringTwo]);
for (int i = 0; i<=(stringOne.length-stringTwo.length); i++) {
NSRange mainRange = NSMakeRange(i, stringTwo.length);
NSString *subString = [stringOne substringWithRange:mainRange];
if ([subString isEqualToString:stringTwo]) {
containsString = YES;
break;
}
}
NSLog(@"%@",containsString?@"Contains String":@"Does not contain String");
}else{
//NSLog(@"Contains Substring: %d",[stringTwo containsString:stringOne]);
for (int i = 0; i<=(stringTwo.length-stringOne.length); i++) {
NSRange mainRange = NSMakeRange(i, stringOne.length);
NSString *subString = [stringTwo substringWithRange:mainRange];
if ([subString isEqualToString:stringOne]) {
containsString = YES;
break;
}
}
NSLog(@"%@",containsString?@"Contains String":@"Does not contain String");
}
not sure if would be ok to use charAt(), if not convert the two string to arrays won't change much in the actual implementation but it would affect time.
private static boolean evaluate(String stringOne, String stringTwo) {
for(int i=0; i<stringOne.length(); i++){
int startIndex = i, counter = 0;
for(int j=0;j<stringTwo.length(); j++){
if(stringOne.charAt(startIndex) == stringTwo.charAt(j)){
startIndex++;
counter++;
}
if(counter == 2){
return true;
}
}
}
return false;
}
public boolean strstr (String src, String target){
if (src.length() < target.length()) return strstr(target,src);
for (int i = 0 ; src.length() - i >= target.length() ; ++i) {
int j = 0 ;
int k = i ;
while (j < target.length() && src.charAt(k) == target.charAt(j)) {
k++;
j++;
}
if (j == target.length()) return true ;
}
return false;
}
class SubstringPresent{
private String largerString = "aaabcdedfd";
private String smallerString = "cdf";
public boolean isSubString(String largerString, String smallerString){
int temp=0;
for(int k = 0; k < largerString.length(); k++){
if(largerString.charAt(k)==smallerString.charAt(temp)){
temp = k;
break;
}
}
int temp_1 = 0;
for(int m = temp; m<largerString.length(); m++){
if(largerString.charAt(m)!=smallerString.charAt(temp_1))
return false;
temp_1++;
if(temp_1 == smallerString.length()){
return true;
}
}
return false;
}
public static void main(String[] args){
SubstringPresent test = new SubstringPresent();
System.out.println(test.isSubString(test.largerString, test.smallerString));
}
}
class SubstringPresent{
private String largerString = "aaabcdedfd";
private String smallerString = "cdf";
public boolean isSubString(String largerString, String smallerString){
int temp=0;
for(int k = 0; k < largerString.length(); k++){
if(largerString.charAt(k)==smallerString.charAt(temp)){
temp = k;
break;
}
}
int temp_1 = 0;
for(int m = temp; m<largerString.length(); m++){
if(largerString.charAt(m)!=smallerString.charAt(temp_1))
return false;
temp_1++;
if(temp_1 == smallerString.length()){
return true;
}
}
return false;
}
public static void main(String[] args){
SubstringPresent test = new SubstringPresent();
System.out.println(test.isSubString(test.largerString, test.smallerString));
}
}
class SubstringPresent{
private String largerString = "aaabcdedfd";
private String smallerString = "cdf";
public boolean isSubString(String largerString, String smallerString){
int temp=0;
for(int k = 0; k < largerString.length(); k++){
if(largerString.charAt(k)==smallerString.charAt(temp)){
temp = k;
break;
}
}
int temp_1 = 0;
for(int m = temp; m<largerString.length(); m++){
if(largerString.charAt(m)!=smallerString.charAt(temp_1))
return false;
temp_1++;
if(temp_1 == smallerString.length()){
return true;
}
}
return false;
}
public static void main(String[] args){
SubstringPresent test = new SubstringPresent();
System.out.println(test.isSubString(test.largerString, test.smallerString));
}
}
class SubstringPresent{
private String largerString = "aaabcdedfd";
private String smallerString = "cdf";
public boolean isSubString(String largerString, String smallerString){
int temp=0;
for(int k = 0; k < largerString.length(); k++){
if(largerString.charAt(k)==smallerString.charAt(temp)){
temp = k;
break;
}
}
int temp_1 = 0;
for(int m = temp; m<largerString.length(); m++){
if(largerString.charAt(m)!=smallerString.charAt(temp_1))
return false;
temp_1++;
if(temp_1 == smallerString.length()){
return true;
}
}
return false;
}
public static void main(String[] args){
SubstringPresent test = new SubstringPresent();
System.out.println(test.isSubString(test.largerString, test.smallerString));
}
}
public boolean strstr (String src, String target){
if (src.length() < target.length()) return strstr(target,src);
for (int i = 0 ; src.length() - i >= target.length() ; ++i) {
int j = 0 ;
while (j < target.length() && src.charAt(i + j) == target.charAt(j)) j++;
if (j == target.length()) return true ;
}
return false;
}
In Java
//aaaabbb aaaaaabbb
//Checking if s1 is a substring of s2 (s1 < s2)
// O(n) - letters in the larger string
public boolean isSubstring(String smallerString, String largerString){
for(int i = 0; i < largerString.length(); ++i){
int endIndex = i + smallerString.length();
if(endIndex > largerString.length())
break;
if(largerString.substring(i, endIndex).equals(smallerString))
return true;
}
return false;
}
public boolean checkSubstring(String s1, String s2){
if(s1.length() < s2.length())
return isSubstring(s1, s2);
//s2 >= s1
return isSubstring(s2, s1);
}
}
the answer is to use boyer-moore or KMP, which ar eboth O(n) algorithms. I'd probably study boyer-moore since it's easier to implement if some crazy interviewer actually wants you to implement an O(n) substring matching.
- Anonymous December 11, 2014