Dropbox Interview Question Software Engineers
Country: United States
we can use a 2-d char. array to store strings and map to the array for each character present in the pattern string
for ex-
arr[0]- 'r' 'e' 'd' '\0' '\0'
arr[1]- 'b' 'l' 'a' 'c' 'k'
.
.
.
and in main program replace it accordingly...
// Global hash table to hold the keys and values
public static Hashtable<Character, String> table = new Hashtable<Character, String>();
public static void main(String[] args) {
// Test
String pat = "aba";
String str = "rocktreerock";
System.out.println(foo(pat, str));
}
public static boolean foo(String pattern, String str) {
// Check for base cases
if (pattern.length() == 0 && str.length() == 0) {
return true;
} else if (pattern.length() > str.length() || pattern.length() == 0) {
return false;
}
// Check if the first char in pattern exists as a key in the hash table
String val = table.get(pattern.charAt(0));
if (val != null) {
// If it does exist, check if it matches with the beginning of str
if (val.equals(str.substring(0, Math.min(val.length(), str.length())))) {
// If it's a match, check the rest of the pattern / string
return foo(pattern.substring(1), str.substring(val.length()));
}
} else {
// Go through every possible value for the first char in pattern
for (int i = 1; i <= str.length() - pattern.length() + 1; i++) {
// Values should be unique so only use it if it's not already in the hash table
if (!table.contains(str.substring(0, i))) {
table.put(pattern.charAt(0), str.substring(0, i));
// Move on to the rest of the problem to see if this key-value pairing works
if (foo(pattern.substring(1), str.substring(i))) {
return true;
} else {
// If the key-value pairing doesn't work, remove it from the hash table
table.remove(pattern.charAt(0));
}
}
}
}
return false;
}
I think the code is correct. I only have some minor suggestions. You should not name the function as "foo". Try to make the function name meaning.
In your program, whenever you call recursive foo(), you create new String. This is not memory efficient. You should update the start index for each string.
backtrack
public boolean checkPattern (String target, String pattern){
HashMap<Character, List<String>> map = new HashMap<> ();
HashMap<Character, Integer> compare = new HashMap<> ();
for (char c : pattern.toCharArray()) {
int count = compare.containsKey(c) ? compare.get(c) + 1 : 1 ;
compare.put(c, count);
}
return helper (target, pattern, 0 , 0, map, compare);
}
private boolean helper (String target , String pattern , int j , int index, HashMap<Character,List<String>> map, HashMap<Character,Integer> compare){
if (j == pattern.length() - 1) {
char p = pattern.charAt(j) ;
String word = target.substring(index, target.length()) ;
boolean f = false ;
if (!map.containsKey(p)) {
List<String> set = new ArrayList<> ();
set.add(word) ;
map.put(p, set);
f = checkResult (compare, map, pattern) ;
map.remove(p);
} else{
String pre = map.get(p).get(0) ;
if (word.equals(pre)) {
map.get(p).add(word);
}
f = checkResult (compare, map, pattern) ;
}
return f ;
}
if (j == pattern.length()) return false ;
boolean flag = false ;
char p = pattern.charAt(j) ;
for (int i = index ; i < target.length() ; ++i) {
String word = target.substring(index, i + 1) ;
if (!map.containsKey(p)) {
List<String> set = new ArrayList<> ();
set.add(word);
map.put(p, set) ;
flag = helper (target, pattern, j + 1, i + 1 ,map ,compare);
map.remove(p) ;
} else{
String pre = map.get(p).get(0) ;
if (word.equals(pre)) {
map.get(p).add(word) ;
flag = helper (target, pattern, j + 1, i + 1, map, compare);
}
}
if (flag) {
return flag ;
}
}
return flag ;
}
private boolean checkResult (HashMap<Character,Integer> compare, HashMap<Character, List<String>> cache, String pattern){
for (char c : pattern.toCharArray()) {
if (compare.get(c) != cache.get(c).size()) {
return false ;
}
}
return true ;
}
Assume L is the length of the string and P is the length of the pattern. Then, we can try to split the string in P substrings and verify the translation. So the size of the problem is C(L, P) ~ L^P.
More precisely, for each character in the pattern, if it already appears earlier, checking is O(L). So we only need to care the unique characters. Assume there are k unique character in the pattern. For each new character, there is maximum L candidates for its translation. Therefore, the complexity is F(P) = L^k.
Python solution:
translations = {}
def patternIsValid(pattern, string):
if len(pattern) == 0 and len(string) == 0:
return True
elif len(pattern) == 0 or len(string) == 0 or len(pattern) > len(string):
return False
# Iterate through pattern 1 char at a time.
# If pattern char is defined already:
if pattern[0] in translations:
translation = translations[pattern[0]]
if ((len(translation) <= len(string)) and (translation == string[:len(translation)])):
return patternIsValid(pattern[1:], string[len(translation):])
# Pattern character not defined. Test all possibilities for this new pattern char
else:
for pSize in range(1, len(string) - len(pattern) + 1):
if string[:pSize] not in translations.values(): # make sure it's unique
translations[pattern[0]] = string[:pSize]
if patternIsValid(pattern[1:], string[pSize:]):
return True
del translations[pattern[0]]
return False
I came up with something similar to the other solutions
bool PatternMatch(char* pPattern, char* pString, std::string* pMap)
{
if (!*pPattern || !*pString)
return (!*pPattern && !*pString);
int mappedSz = pMap[*pPattern].size();
if (mappedSz)
{
if (mappedSz > (int)strlen(pString))
return false;
const char* pMapped = pMap[*pPattern].c_str();
for (int i = 0; i < mappedSz; i++)
if (pMap[*pPattern][i] != pString[i])
return false;
return PatternMatch(pPattern+1, pString + mappedSz, pMap);
}
for (int i = 0; i < (int)strlen(pString); i++)
{
pMap[*pPattern].assign(pString, i+1);
if (PatternMatch(pPattern+1, pString + i + 1, pMap))
return true;
}
pMap[*pPattern].clear();
return false;
}
void main()
{
char buf[128], buf2[128];
while(1)
{
printf("Enter string:");
gets(buf);
printf("\nEnter pattern:");
gets(buf2);
std::string patMap[256];
if (PatternMatch(buf2, buf, patMap))
{
printf("Passed: ");
for (int i = 0; i < (int)strlen(buf2); i++)
printf("%s,", patMap[buf2[i]].c_str());
printf("\n");
}
else
printf("Failed\n");
}
}
patternMap={}
currentPattern={}
def findPattern(pattern, str):
p = pattern[0]
if p in currentPattern:
pstr = currentPattern[p]
if str.find(pstr) == 0:
if len(pattern)==1:
if len(pstr)==len(str):
return True
else:
return False
else:
return findPattern(pattern[1:len(pattern)], str[len(pstr):len(str)])
else:
return False
else:
for i in xrange(len(str)):
pstr = str[0:i+1]
if p not in patternMap:
patternMap[p] = [pstr]
else:
if pstr in patternMap[p]:
continue
else:
patternMap[p].append(pstr)
currentPattern[p] = pstr
ret = findPattern(pattern[1:len(pattern)], str[i+1:len(str)])
if ret==True:
return ret
else:
currentPattern.pop(p)
continue
return False
Adding a Java implementation:
public static boolean matches(String pattern, String str) {
return matches_rec(pattern, str, new HashMap<>());
}
private static boolean matches_rec(String pattern, String str, HashMap<Character, String> dict) {
if ("".equals(pattern) && "".equals(str)) {
return true;
} else if ("".equals(pattern) && !"".equals(str) || !"".equals(pattern) && "".equals(str)) {
return false;
}
char currPattern = pattern.charAt(0);
String translation = dict.get(currPattern);
if (translation == null) {
for (int i = 1; i <= str.length(); i++) {
dict.put(currPattern, str.substring(0, i));
boolean matches = matches_rec(pattern.substring(1), str.substring(i, str.length()), dict);
if (matches) {
return true;
}
}
dict.remove(currPattern);
return false;
}
if (str.startsWith(translation)) {
return matches_rec(pattern.substring(1), str.substring(translation.length()), dict);
}
return false;
}
{
public static bool T(string pattern, string word)
{
if (pattern.Length == 1)
{
if (dict.ContainsKey(pattern))
{
if (dict[pattern] == word)
return true;
else
return false;
}
else
return true;
}
var s = "";
for (int i = 0; i <word.Length-1 ; i++)
{
s += word[i];
if (!dict.ContainsKey(pattern[0].ToString()))
{
dict.Add(pattern[0].ToString(), s);
}
else if (dict[pattern[0].ToString()] != s)
{
continue;
}
var res = T(pattern.Substring(1), word.Substring(i + 1));
if (res)
{
return true;
}
else
{
dict.Remove(pattern[0].ToString());
}
}
return false;
}
}
simple c# implementation
public static bool T(string pattern, string word)
{
if (pattern.Length == 1)
{
if (dict.ContainsKey(pattern))
{
if (dict[pattern] == word)
return true;
else
return false;
}
else
return true;
}
var s = "";
for (int i = 0; i <word.Length-1 ; i++)
{
s += word[i];
if (!dict.ContainsKey(pattern[0].ToString()))
{
dict.Add(pattern[0].ToString(), s);
}
else if (dict[pattern[0].ToString()] != s)
{
continue;
}
var res = T(pattern.Substring(1), word.Substring(i + 1));
if (res)
{
return true;
}
else
{
dict.Remove(pattern[0].ToString());
}
}
return false;
}
patternMap={}
currentPattern={}
def findPattern(pattern, str):
p = pattern[0]
if p in currentPattern:
pstr = currentPattern[p]
if str.find(pstr) == 0:
if len(pattern)==1:
if len(pstr)==len(str):
return True
else:
return False
else:
return findPattern(pattern[1:len(pattern)], str[len(pstr):len(str)])
else:
return False
else:
for i in xrange(len(str)):
pstr = str[0:i+1]
if p not in patternMap:
patternMap[p] = [pstr]
else:
if pstr in patternMap[p]:
continue
else:
patternMap[p].append(pstr)
currentPattern[p] = pstr
ret = findPattern(pattern[1:len(pattern)], str[i+1:len(str)])
if ret==True:
return ret
else:
currentPattern.pop(p)
continue
return False
What you can do here is a recursive solution where each "level" handles a single pattern key (handles a single index in the pattern key string - for instance, level 1 handles 'a', than level 2 handles 'b', than level 3 handles 'a').
Each level is responsible to create a string (substring) candidate for the pattern key if the later hasn't appeared before or to look for the same substring if the partner key has appeared before.
Here is a python solution
- daniel.a.p March 03, 2015def match(pattern, str): matches = dict() return _match(pattern[:], str, 0, 0, matches), matches def _match(pattern, str, current_ptrn, str_start, matches): if current_ptrn == len(pattern): if str_start == len(str): return True else: return False if pattern[current_ptrn] in matches: for str_end in range(str_start + 1, len(str) + 1): if matches[pattern[current_ptrn]] == str[str_start:str_end]: if _match(pattern, str, current_ptrn + 1, str_end, matches): return True else: for str_end in range(str_start + 1, len(str) + 1): matches[pattern[current_ptrn]] = str[str_start:str_end] if _match(pattern, str, current_ptrn + 1, str_end, matches): return True del matches[pattern[current_ptrn]] return False