Interview Question
Country: United States
bool isSpecialSubstring(std::string mainStr, std::string substr)
{
if (mainStr.size() < substr.size())
{
return false;
}
int mainStrStartIndex = 0;
for (char c : substr)
{
auto nextCharIndex = mainStr.find(c, mainStrStartIndex);
if (nextCharIndex == std::string::npos)
{
return false;
}
else
{
mainStrStartIndex = nextCharIndex;
}
}
return true;
}
public static void main(String[] args){
String s1 = "abcdefg";
String s2 = "acb";
System.out.println(lcs(s1, s2));
}
public static boolean lcs(String s1, String s2){
int n = s1.length();
int m = s2.length();
int[][] dp = new int[n+1][m+1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s1.charAt(i-1) == s2.charAt(j-1))
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
int len = dp[n][m];
if(len == m)
return true;
return false;
}
O(N) solution:
#include "CommonHeader.h"
// O(N) solution
bool isSubstring(const std::string& str, const std::string& sub)
{
std::string tmpSub = sub;
size_t i = 0;
while(!tmpSub.empty()) {
char ch = tmpSub.front();
for(; i < str.length(); ++i) {
if(str[i] == ch) {
tmpSub.erase(tmpSub.begin());
break;
}
}
if(i < str.length()) {
// we got more chars to scan in the input string
continue;
} else {
// we scanned the entire input string
// break and return true if we found all characters in "sub"
// false otherwise (i.e. return tmpSub.empty())
break;
}
}
return tmpSub.empty();
}
def check_dest(dest):
des_len = len(dest) - 1
i = 0
j = 0
while i < des_len and j <= des_len:
j = i + 1
if dest[i] > dest[j]:
return False
i += 1
def is_special_substring(org, dest):
dest_len = len(dest)
flag = 0
val = check_dest(dest)
if val == False:
return False
else:
for j in dest:
for i in org:
if j == i:
flag += 1
break
if flag == 3:
return True
def main():
val = is_special_substring('abcdefg', 'bad')
if val:
print("True")
else:
print("False")
if __name__ == '__main__':
main()
public static boolean isSpecialSubString(String s1, String s2) {
if (s1 != null && s2 != null) {
int k = 0;
String check = "";
for (int i = 0; i < s2.length(); i++) {
for (int j = k; j < s1.length(); j++) {
if (s1.charAt(j) == s2.charAt(i)) {
k = j;
check += s1.charAt(j);
break;
}
}
}
if (check.equals(s2)) {
return true;
}
}
return false;
}
import java.util.Scanner;
public class SpecialSequenceCareerCup {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s1 = sc.next();
String s2= sc.next();
boolean x= isSpecialSubString(s1,s2);
System.out.println(x);
}
public static boolean isSpecialSubString(String st1,String st2){
int j;
int lastindex=Integer.MIN_VALUE;
boolean result=false;
for(int i=0; i<st2.length();i++){
j=st1.lastIndexOf(st2.charAt(i));
if(j>lastindex){
lastindex=j;
}
if(j<0){
System.out.println("sequence is not available");
result= false;
}
else{
if(lastindex==j && st2.length()==i+1){
result= true;
}
else if(lastindex<j)
{
result= false;
}
}
}
return result;
}
}
class SpecialStringProblem
{
public static void main(String[] args){
String firstStringS1 = "abcdefgh";
String SecondStringS2 = "acb"; //"abg";
boolean isSpecial = isSpecialSubstring(firstStringS1, SecondStringS2);
System.out.println("Special String : " + isSpecial);
}
public static boolean isSpecialSubstring(String firstStringS1,String SecondStringS2){
int s1Len = firstStringS1.length();
int s2Len = SecondStringS2.length();
int j=0;
for(int i=0; i<s1Len && j < s2Len; i++){
if(firstStringS1.charAt(i) == SecondStringS2.charAt(j)){
j++;
}
}
if(j == s2Len){
return true;
}else{
return false;
}
}
}
public class SpecialString {
/*
Given two strings s1, s2, write a function that returns true if s2 is a special substring
s1. A special substring s2 is such that the s1 contains s2 where each character in s2 appears in
sequence in s1, but there can be any characters in s1 in between the sequence.
Example:
isSpecialSubstring('abcdefg', 'abc') => true
isSpecialSubstring('abcdefg', 'acg') => true
isSpecialSubstring('abcdefg', 'acb') => false;
The first two are abc and acg appears in 'abcdefg' in that order, although there might be multiple chars between the next
character in s2. The last one is false, because in 'acb' the character 'b' appears before the character 'c' in 'abcdefg'
Hope thats clear.
* */
public static void main(String[] args) {
System.out.println("Here is my the answer case 1:"+isSpecialSubstring("abcdefg", "abc"));
System.out.println("Here is my the answer case 2:"+isSpecialSubstring("abcdefg", "acg"));
System.out.println("Here is my the answer case 3:"+isSpecialSubstring("abcdefg", "acb"));
}
public static boolean isSpecialSubstring(String original, String theSubString){
if(original.indexOf(theSubString, 0) !=-1){ return true;
}else{
String order = "";
for(int i =0;i<original.length();i++){
String c = String.valueOf(original.charAt(i));
if(theSubString.contains(c)) order = order.concat(c);
}
if(order.indexOf(theSubString, 0) !=-1)return true;
}
return false; }
}
- Alex September 23, 2017