Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Fine solution when the difference is 1 character. When we have to search for difference >1, prefix tree is better.
#include <iostream>
#include <vector>
using namespace std;
// To execute C++, please define "int main()"
bool isOneCharDiffStringExist(vector<string> list, string s)
{
int length = (int)list.size();
if(length == 0 || s.size() ==0)
return false;
for(int i=0;i<length;i++)
{
if(list[i].size()!=s.size())
continue;
bool oneCharDiffFound = false;
for(int j =0;j<(int)list[i].size();j++)
{
if(list[i][j] != s[j] )
{
if(!oneCharDiffFound)
oneCharDiffFound = true;
else
{
oneCharDiffFound = false;
break;
}
}
}
if(oneCharDiffFound)
return true;
}
return false;
}
int main() {
vector<string> list;
list.push_back("bana");
list.push_back("apple");
list.push_back("banacb");
list.push_back("bonanza");
list.push_back("banamf");
cout<<isOneCharDiffStringExist(list,"banana");
return 0;
}
May be we can construct a prefix tree. And than run a dfs with parameter 1 from the root, which will go to the child if and only if the path to that node is equal to a some prefix or you have one point (parameter) which you can use to go to this child if the path to parent equal to some prefix but the letter in child doesn't equal to the next letter in string.
One should be careful when to return true. I thought the task asked that the difference is at most 1. But after re-reading think we should find the difference equal exactly 1.
So when we traverse prefix tree and parameter == 0 and we find some node, then we can return true. But if parameter stays 1, we have to search further, because all characters are equal so far.
May be we can construct a prefix tree. And than run a dfs with parameter 1 from the root, which will go to the child if and only if the path to that node is equal to a some prefix or you have one point (parameter) which you can use to go to this child if the path to parent equal to some prefix but the letter in child doesn't equal to the next letter in string.
- Brute force solution comes out to be O(n^2) i.e you go through each string and compare char by char then if difference of char > 1 you break out of the loop so on.
- Another approach : finding edit distance but thats O(n^2) so if we do it for each string in array then it would be O(n^3)
- Third approach longest subsequence - that is also O(n^2) so overall running time is O(n^3).
If the query is frequent, we can use a Trie to store the array of string. I omit the code of build Trie for simplify
struct Node {
bool exist;
Node *children[256];
};
Node *root;
bool dfs(Node *n, const string &s, int pos, int cnt) {
if (cnt > 1)
return false;
if (pos == s.size())
return cnt == 1;
for (int i = 0; i < 256; ++i) {
Node *c = n->children[i];
if (c != nullptr) {
if (s[pos] == i && dfs(c, s, pos + 1, cnt) ||
s[pos] != i && dfs(c, s, pos + 1, cnt + 1))
return true;
}
}
}
bool hasSimilar(const string &s) {
return dfs(root, s, 0, 0);
}
//Assumption: The word which is 1 character different from the query string may not have its characters in the same order as that of the query string.
public boolean hasSimilarWord(String[] arr,String s)throws NullPointerException;
{
if(arr==null||s==null)
{
throw new NullPointerException();
}
return isOneCharDiff(s,arr);
}
private boolean isOneCharDiff(String s,String[] words)
{
//Examine each word and see if there's one which only differs by 1 character
for(int i=0;i<words.length;i++)
{
String x=words[i].length();
if(x==s.length())
{
//Create a HashMap of all the characters in this string
HashMap<Character,Integer> mp=new HashMap<Character,Integer>();
for(int i=0;i<x.length();i++)
{
if(!mp.containsKey(x.charAt(i)))
{
mp.put(x.charAt(i),1);
}else
{
int currCount=mp.get(x.charAt(i)).intValue();
mp.put(x.charAt(i),++currCount);
}
}
//Check query word against characters in hash map
for(int j=0;j<s.length();j++)
{
if(mp.containsKey(s.charAt(j))
{
int currCount=mp.get(s.charAt(j)).intValue();
--currCount;
if(currCount==0)
{
mp.remove(s.charAt(j));
}else
{
mp.put(s.charAt(j),currCount);
}
}
}
if(mp.size()==1)
{
return true;//If we find a string that differs by just one character, return true.
}
}
}
return false;
}
//Time complexity: O(kn)--From comparing whether each string has matching characters with the query string (k is the number of strings whose length matches the query string, n is the number of characters in the query string).Space complexity O(k+n)--From the list of words with the same length as the query string and the hash map of characters.
public class OneOff {
private static boolean isOffByOne(String main, String sub) {
if (main==null || sub == null || main.length() != sub.length())
return false;
boolean oneOff= false;
for (int i=0;i<main.length(); i++) {
if (main.charAt(i) != sub.charAt(i))
{
if (!oneOff) oneOff=true;
else return false;
}
}
return oneOff;
}
public static boolean findOfByOne(String str, String[] candidates)
{
if (str==null || str.length() <1 || candidates.length ==0 )
return false;
for (int i=0;i <candidates.length; i++) {
boolean isOff = isOffByOne(str, candidates[i]);
if (isOff) return true;
}
return false;
}
public static void main(String[] args) {
String[] cands = {"bana", "apple", "banaba", "bonanza", "banamf" };
System.out.println(findOfByOne("banana", cands));
}
}
Simple sample solution in Python:
Increased space complexity because of additional dictionary for counting common chars for each string
def diff_one(s1, list):
dict = {}
for i in list:
dict[i]=0
for i,j in enumerate(s1):
for k in list:
if i <len(k) and j==k[i]:
dict[k]+=1
if len( filter(lambda x: x>len(s1)-2,dict.values()) ):
return True
if __name__=="__main__":
if diff_one("banana", ["bana", "apple", "banaba", "bonanza", "banamf", "bananaa"] ):
print "found"
else:
print "not found"
We can build a trie of n strings in O(n) time if we assume that strings are of limited length dictionary words and alphabet size is limited (e.g. 256). Then there is a O(n) solution using the Trie.
After the trie has been built then for any given search word search down the word in the trie. If we find that there is no child in the current trie node for the current character at i of the search string, then we allow to the mismatch and go down to all the childs (maxm (256-1)=255). Now, we search for next character in all the child and stop as soon as we found a mismatch again. This way we will exhaust the search string and we check each of the current nodes in the trie (maxm 255) if it it contains an end word. If yes, then the words at those nodes are the result.
The worst case complexity assuming constant A of alphabet size and maximum string length K - is when we have mismatch in first position and the root node contains a node for all letters in the alphabet but the first character in the search string. So worst case complexity for search is (A-1)*(K-1) = O(K).
If the search word is banana and the array is
[aanana, canana, danana, eanana ....... zanana]
then in this case using your trie method would have a time complexity of O(NK) to find all such strings where N is number of strings in array and K is the max length of any string.
Please correct me if I am wrong.
If you think about real english word search then we can consider length of search word within a max limit i.e. O(1) length. Then the search through each path will be constant and overall complexity is of course can't be less then O(n).
/*program to find string with one difference character */
#define ROW 5
#define COLUMN 20
#include<stdio.h>
#include<string.h>
int main()
{
char str[ROW][COLUMN],check[COLUMN];
int i,j,x,y,a,k;
printf("Enter 5 words:\n");
while(i<ROW) //while loop to enter elements in the string array.
{
scanf("%s",str[i++]);
} //end of whil loop.
printf("Enter string to check:\n");
scanf("%s",check);
i=0;
printf("check string : %s\n",check);
x=strlen(check);
i=0;
k=0;
while(k < 5) //begining of main while loop.
{
y=strlen(str[k]);
if(x==y)
{
if (strcmp(check,str[k])==0) //begining of inner if.
{
// printf("string matched:%s\n",str[k]);
} //end of inner if.
else // begining of inner else
{
a=0;
for(j=0;j<x;j++) //for loop for going character wise match of each string.
{
if(check[j]!= str[k][j])
{
a++;
}
} // end of for loop.
if(a==1)
{
printf("Element found:%s\n",str[k]);
}
} //end of inner else.
} //end of outter if.
k++;
} // end of main while loop.
return 0;
} // end of main().
/*program to find string with one difference character */
#define ROW 5
#define COLUMN 20
#include<stdio.h>
#include<string.h>
int main()
{
char str[ROW][COLUMN],check[COLUMN];
int i,j,x,y,a,k;
printf("Enter 5 words:\n");
while(i<ROW) //while loop to enter elements in the string array.
{
scanf("%s",str[i++]);
} //end of whil loop.
printf("Enter string to check:\n");
scanf("%s",check);
i=0;
printf("check string : %s\n",check);
x=strlen(check);
i=0;
k=0;
while(k < 5) //begining of main while loop.
{
y=strlen(str[k]);
if(x==y)
{
if (strcmp(check,str[k])==0) //begining of inner if.
{
// printf("string matched:%s\n",str[k]);
} //end of inner if.
else // begining of inner else
{
a=0;
for(j=0;j<x;j++) //for loop for going character wise match of each string.
{
if(check[j]!= str[k][j])
{
a++;
}
} // end of for loop.
if(a==1)
{
printf("Element found:%s\n",str[k]);
}
} //end of inner else.
} //end of outter if.
k++;
} // end of main while loop.
return 0;
} // end of main().
Simple python solution-- linear runtime and constant space
def oneCharDiff(arr, root):
length = len(root)
for word in arr:
differences = 0
if length != len(word):
continue
for i in range(length):
if word[i] != root[i]:
differences += 1
if differences == 1:
return True
return False
import java.util.Scanner;
public class StringDifference {
public void inputString(String checkThisString, String s){
int j = 0;
for(int i=0;i<checkThisString.length();i++){
if(checkThisString.length()!= s.length()){
System.out.println("False");
break;
}
if(checkThisString.charAt(i) != s.charAt(i)){
j++;
if(j ==2){
System.out.println("more difference than 2");
break;
}
}
if(i== checkThisString.length()-1 && j==1){
System.out.println("true");
break;
}
}
}
public void isOneCharDiff(String inputString, String []words){
int counter = 0;
for(int i=0; i<words.length;i++){
String x = words[i];
int wordLength = x.length();
for(int j=0;j<wordLength;j++){
if(inputString.length() != wordLength){
System.out.println("length not equal of " + x +" and " + inputString);
break;
}
if(inputString.charAt(j) != x.charAt(j)){
counter++;
if(counter == 2){
System.out.println("More than 2 different characters between strings " + x + " and " + inputString);
counter = 0;
break;
}
}
if(j == inputString.length()-1 && counter ==1){
System.out.println("one difference found between String " + x + " and " + inputString);
counter = 0;
break;
}
}
}
}
public static void main(String[] args) {
//string difference
StringDifference stringDifference = new StringDifference();
Scanner scanner = new Scanner(System.in);
System.out.println("Enter String to compare ! \n");
String checkThisString = scanner.nextLine();
System.out.println("Enter String to be compared ! \n");
String s = scanner.nextLine();
stringDifference.inputString(checkThisString, s);;
String wordsArray[] = { "bananaa","bannna","bannan", "mmmmmm"};
stringDifference.isOneCharDiff(checkThisString, wordsArray);
}
}
Find the one statement solution.
bool FindSingleCharDiff(const string& input, const vector<string> &listInputs)
{
int count = count_if(listInputs.begin(), listInputs.end(), [&input](const string &each)
{
int bRet = false;
if (input.size() != each.size())
{
bRet = false;
}
else if (input.compare(each) == 0)
{
bRet = true;
}
else
{
int index = -1;
int diffCount = count_if(each.begin(), each.end(), [&input, &index](const char ch)
{
index++;
return (input.at(index) != ch);
});
bRet = diffCount <= 1;
}
return bRet;
});
return count > 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
string text("banana");
vector<string> listText = { "banaba", "banaaa", "apple" };
bool ans = FindSingleCharDiff(text, listText);
return 0;
}
Java implementation in linear time and essentially constant space
Mapping original string to a hasmap, then removing from a copy of it for each item in array to determine if matches 3 possibilities. Logic is commented in code
import java.util.HashMap;
/*
*
* Given a string and array of strings, find whether the array contains a string with one character difference from the given string. Array may contain string of different lengths.
Ex: Given string banana
and array is [bana, apple, banaba, bonanza, banamf]
and the outpost should be true as banana and banaba are one character difference.
*
*
* n = total number of characters in all input
* m = average length of a string
* Performance = O(n)
* Storage = O(2m) at any given time
*/
public class OffByOne {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input = "abcde";
String[] array = {"ebcda"};
System.out.println(OffByOne(input, array));
}
static boolean OffByOne(String string, String[] array){
HashMap<Character, Integer> map = mapChars(string);
String current;
for(int i=0;i<array.length;i++){
current = array[i];
if(Math.abs(string.length()-current.length())>1)
continue;
else{
HashMap<Character, Integer> copy = new HashMap<Character, Integer>(map);
for(int j = 0;j<current.length();j++){
Integer val = copy.get(current.charAt(j));
if(val==null)
continue;
else{
if(val==1)
copy.remove(current.charAt(j));
else
copy.put(current.charAt(j), val-1);
}
}
//array's string is same except it has 1 more char = map will have only 0 element remaining, string size diff by 1
if(current.length()-string.length()==1 && copy.size()==0)
return true;
//1 less char = map only has 1 element left, length diff by 1
if(current.length()-string.length()==-1 && copy.size()==1)
return true;
//1 substituted char = same length and 1 element left in map
if(current.length()==string.length() && copy.size()==1)
return true;
}
}
return false;
}
static HashMap<Character, Integer> mapChars(String string){
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0;i<string.length();i++){
Character c = string.charAt(i);
Integer num = map.get(c);
if(num==null)
map.put(c, 1);
else
map.put(c,num+1);
}
return map;
}
}
import java.util.HashMap;
/*
*
* Given a string and array of strings, find whether the array contains a string with one character difference from the given string. Array may contain string of different lengths.
Ex: Given string banana
and array is [bana, apple, banaba, bonanza, banamf]
and the outpost should be true as banana and banaba are one character difference.
*
*
* n = total number of characters in all input
* m = average length of a string
* Performance = O(n)
* Storage = O(2m) at any given time
*/
public class OffByOne {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input = "abcde";
String[] array = {"ebcda"};
System.out.println(OffByOne(input, array));
}
static boolean OffByOne(String string, String[] array){
HashMap<Character, Integer> map = mapChars(string);
String current;
for(int i=0;i<array.length;i++){
current = array[i];
if(Math.abs(string.length()-current.length())>1)
continue;
else{
HashMap<Character, Integer> copy = new HashMap<Character, Integer>(map);
for(int j = 0;j<current.length();j++){
Integer val = copy.get(current.charAt(j));
if(val==null)
continue;
else{
if(val==1)
copy.remove(current.charAt(j));
else
copy.put(current.charAt(j), val-1);
}
}
//array's string is same except it has 1 more char = map will have only 0 element remaining, string size diff by 1
if(current.length()-string.length()==1 && copy.size()==0)
return true;
//1 less char = map only has 1 element left, length diff by 1
if(current.length()-string.length()==-1 && copy.size()==1)
return true;
//1 substituted char = same length and 1 element left in map
if(current.length()==string.length() && copy.size()==1)
return true;
}
}
return false;
}
static HashMap<Character, Integer> mapChars(String string){
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0;i<string.length();i++){
Character c = string.charAt(i);
Integer num = map.get(c);
if(num==null)
map.put(c, 1);
else
map.put(c,num+1);
}
return map;
}
}
import java.util.HashMap;
/*
*
* Given a string and array of strings, find whether the array contains a string with one character difference from the given string. Array may contain string of different lengths.
Ex: Given string banana
and array is [bana, apple, banaba, bonanza, banamf]
and the outpost should be true as banana and banaba are one character difference.
*
*
* n = total number of characters in all input
* m = average length of a string
* Performance = O(n)
* Storage = O(2m) at any given time
*/
public class OffByOne {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input = "abcde";
String[] array = {"ebcda"};
System.out.println(OffByOne(input, array));
}
static boolean OffByOne(String string, String[] array){
HashMap<Character, Integer> map = mapChars(string);
String current;
for(int i=0;i<array.length;i++){
current = array[i];
if(Math.abs(string.length()-current.length())>1)
continue;
else{
HashMap<Character, Integer> copy = new HashMap<Character, Integer>(map);
for(int j = 0;j<current.length();j++){
Integer val = copy.get(current.charAt(j));
if(val==null)
continue;
else{
if(val==1)
copy.remove(current.charAt(j));
else
copy.put(current.charAt(j), val-1);
}
}
//array's string is same except it has 1 more char = map will have only 0 element remaining, string size diff by 1
if(current.length()-string.length()==1 && copy.size()==0)
return true;
//1 less char = map only has 1 element left, length diff by 1
if(current.length()-string.length()==-1 && copy.size()==1)
return true;
//1 substituted char = same length and 1 element left in map
if(current.length()==string.length() && copy.size()==1)
return true;
}
}
return false;
}
static HashMap<Character, Integer> mapChars(String string){
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0;i<string.length();i++){
Character c = string.charAt(i);
Integer num = map.get(c);
if(num==null)
map.put(c, 1);
else
map.put(c,num+1);
}
return map;
}
}
public static boolean checkString(String string, String[] array) {
if (array.length > 0 && string.length() > 0) {
for (String s : array) {
if (s.length() == string.length()) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == string.charAt(i)) {
count++;
}
}
if (count == string.length() - 1) {
return true;
}
}
}
} else {
System.err.println("program error");
}
return false;
}
public static boolean checkString(String string, String[] array) {
if (array.length > 0 && string.length() > 0) {
for (String s : array) {
if (s.length() == string.length()) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == string.charAt(i)) {
count++;
}
}
if (count == string.length() - 1) {
return true;
}
}
}
} else {
System.err.println("program error");
}
return false;
}
#include<stdio.h>
#include<string.h>
void main()
{
char *fruits[5] = {"bana", "apple", "banaba", "abnaba", "banamf" };
char fruit[10] = "banana";
unsigned int i,j,count = 0;
//printf("Enter fruit na");
for(i = 0; i < 5; i++)
{
if(strlen(fruits[i]) == strlen(fruit))
{
for(j = 0; j < strlen(fruit); j++)
{
if(fruits[i][j] != fruit[j])
{
if( count > 1)
break;
else
count++;
}
}
count = 0;
printf("%s\t",fruits[i]);
}
}
}
#include<stdio.h>
#include<string.h>
void main()
{
char *fruits[5] = {"bana", "apple", "banaba", "abnaba", "banamf" };
char fruit[10] = "banana";
unsigned int i,j,count = 0;
//printf("Enter fruit na");
for(i = 0; i < 5; i++)
{
if(strlen(fruits[i]) == strlen(fruit))
{
for(j = 0; j < strlen(fruit); j++)
{
if(fruits[i][j] != fruit[j])
{
if( count > 1)
break;
else
count++;
}
}
count = 0;
printf("%s\t",fruits[i]);
}
}
}
What I wrote, without cheating:
1. put all the words from array into an R-way Trie;
– Trie should support wildcard matching ('?' symbol)
2. generate an array of words with one '?' wildcard symbol at each position of the input word;
3. if any word generated at step 2 can be found in a Trie – return true, false - otherwise.
Code:
class StringDifference {
static boolean have1CharDifference(String in, String[] arr){
/* first we could filter out strings of different length,
put the rest in a prefix tree */
Trie trie = new Trie();
for (String s: arr)
if(in.length() == s.length()) { trie.add( s ); }
/* match each word from the list (*) against this trie */
for (String s: generateWildcardStrings(in))
if ( trie.contains(s) ) { return true; }
return false;
}
/* (*) generates an array of strings with single wildcard
symbol at each position of the input string */
static String[] generateWildcardStrings(String s) {
String[] result = new String[s.length()];
for (int i=0; i< s.length(); i++) {
char[] arr = s.toCharArray();
arr[i] = '?';
result[i] = new String(arr);
}
return result;
}
}
class Trie { // R-way trie
private final int a_letter = (int)'a',
z_letter = (int)'z',
R = z_letter - a_letter + 1;
private Node root = new Node();
private class Node { Node[] nodes = new Node[R]; }
public void add(String word) {
Node current = root;
for (int c: word.toCharArray()){
int ix = c - a_letter;
if (current.nodes[ix] == null) { current.nodes[ix] = new Node(); }
current = current.nodes[ix]; // go down the prefix tree
}
}
public boolean contains(String word) {
Node current = root;
char[] inWord = word.toCharArray();
for (int i=0; i<inWord.length; i++){
if (inWord[i] == '?') { // treat the wildcard differently
// if this is the last symbol - return true
if (i == inWord.length-1) { return true; }
else { // else - look ahead 1 symbol
int ix = inWord[i+1] - a_letter;
int j=0;
for (; j<R; j++) {
if (current.nodes[j] != null
&& current.nodes[j].nodes[ix] != null) {
current = current.nodes[j]; // go down the tree
}
}
/* if none of the sub-branches matches
the given letter - return false */
if ( j == R-1 ) { return false; }
}
} else { // process a normal letter
int ix = inWord[i] - a_letter;
if (current.nodes[ix] == null) { return false; }
current = current.nodes[ix]; // go down the tree
}
}
return true;
}
}
This approach is good but implies that input and target strings have the same length which is not mentioned in the description.
However, it might be applied to different lengths strings, but generateWildcardStrings method needs to be modified in this case, for example:
- add '*' symbol to (target.Lenght + 1) positions to specify one additional character
- add '\' symbol to (target.Lenght) positions to specify one missing character
/* To my understanding:
1. the interviewer actually asked for the same array, how to make queries fast - each using different word.
If for only one time query, brutal force word by word comparison should work.
2. two words one char different means:
a. they are the same length but one char is different. OR
b. one is one char shorter or longer than the other.
Below is java code using trie and dfs.
*/
public class GG_OneOffCompare {
class DepMinMax {
int max;
int min;
DepMinMax(int max, int min)
{
this.max = max;
this.min = min;
}
}
class Node {
char ch;
ArrayList<Node> children;
int minDep;
int maxDep;
Node(char ch)
{
this.ch = ch;
children = new ArrayList<>();
this.minDep = this.maxDep = 1;
}
boolean isSentinel()
{
return children.size() == 0;
}
boolean isBeforeSentinel()
{
for(int i=0; i<children.size(); ++i)
{
if(children.get(i).isSentinel())
return true;
}
return false;
}
}
boolean query(String[] arr, String word) {
Node trie = buildTrie(arr);
getDepth(trie);
print(trie, "");
for(int i=0; i<trie.children.size(); ++i) {
if(queryEqualLength(trie.children.get(i), word, false))
return true;
if(queryShorterLength(trie.children.get(i), word, false))
return true;
if(queryLongerLength(trie.children.get(i), word, false))
return true;
}
return false;
}
boolean queryShorterLength(Node trie, String word, boolean alreadyOneOff) {
// check if there is a word in the trie that is one char shorter
if (trie.isSentinel())
return (alreadyOneOff && word.length() == 0) ||
(!alreadyOneOff && word.length() == 1);
if (alreadyOneOff) {
if (word.length() < trie.minDep - 1 || trie.maxDep - 1 < word.length())
return false;
} else {
if (word.length() - 1 < trie.minDep - 1 || trie.maxDep - 1 < word.length() - 1)
return false;
}
if (trie.ch == word.charAt(0)) {
for (int i = 0; i < trie.children.size(); ++i) {
if (alreadyOneOff) {
if (queryShorterLength(trie.children.get(i), word.substring(1), true))
return true;
} else {
if (queryShorterLength(trie.children.get(i), word.substring(1), false) ||
queryShorterLength(trie, word.substring(1), true))
return true;
}
}
} else {
if (alreadyOneOff) return false;
for (int i = 0; i < trie.children.size(); ++i) {
if (queryShorterLength(trie, word.substring(1), true))
return true;
}
}
return false;
}
boolean queryLongerLength(Node trie, String word, boolean alreadyOneOff) {
// check if there is a word in the trie that is one char longer than the parameter word
if (word.length() == 0)
return (alreadyOneOff && trie.isSentinel()) ||
(!alreadyOneOff && trie.isBeforeSentinel());
if (alreadyOneOff) {
if (word.length() < trie.minDep - 1 || trie.maxDep - 1 < word.length())
return false;
} else {
if (word.length() + 1 < trie.minDep - 1 || trie.maxDep - 1 < word.length() + 1)
return false;
}
if (trie.ch == word.charAt(0)) {
for (int i = 0; i < trie.children.size(); ++i) {
if (alreadyOneOff) {
if (queryShorterLength(trie.children.get(i), word.substring(1), true))
return true;
} else {
if (queryLongerLength(trie.children.get(i), word.substring(1), false) ||
queryLongerLength(trie.children.get(i), word, true))
return true;
}
}
} else {
if (alreadyOneOff) return false;
for (int i = 0; i < trie.children.size(); ++i) {
if (queryLongerLength(trie.children.get(i), word, true))
return true;
}
}
return false;
}
boolean queryEqualLength(Node trie, String word, boolean alreadyOneOff)
{
// check if there is a word in trie that have the
// same length as the parameter word but one char different.
if(trie.isSentinel())
return (alreadyOneOff && word.length() == 0);
if(word.length() < trie.minDep-1 || trie.maxDep-1 < word.length())
return false;
// pre-order dfs
if(trie.ch == word.charAt(0))
{
for(int i=0; i<trie.children.size(); ++i) {
if (queryEqualLength(trie.children.get(i), word.substring(1), alreadyOneOff))
return true;
}
}
else
{
if (alreadyOneOff) return false;
for(int i=0; i<trie.children.size(); ++i) {
if (queryEqualLength(trie.children.get(i), word.substring(1), true))
return true;
}
}
return false;
}
void print(Node trie, String buf) {
if(trie.isSentinel()) {
System.out.println(buf + trie.ch);
return;
}
buf = buf + trie.ch + ",";
for(int i=0; i<trie.children.size();++i)
{
print(trie.children.get(i), buf);
}
}
// get min and max depths for each node.
DepMinMax getDepth(Node trie)
{
// postorder DFS
if(trie.isSentinel())
return new DepMinMax(1, 1);
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int i=0; i<trie.children.size(); ++i)
{
DepMinMax dep = getDepth(trie.children.get(i));
min = Math.min(min, dep.min);
max = Math.max(max, dep.max);
}
trie.maxDep = max + 1;
trie.minDep = min + 1;
return new DepMinMax(trie.maxDep, trie.minDep);
}
Node buildTrie(String[] arr) {
Node root = new Node('#');
for(int i=0; i<arr.length; ++i)
{
buildTreeHelper(root, arr[i]);
}
return root;
}
void buildTreeHelper(Node root, String s)
{
if(s.length() == 0) {
root.children.add(new Node('$')); //important: add sentinel node - required.
return;
}
Node child = null;
for(int i=0; i<root.children.size(); ++i)
{
if(root.children.get(i).ch == s.charAt(0))
{
child = root.children.get(i);
break;
}
}
if(child == null)
{
Node s0Node = new Node(s.charAt(0));
root.children.add(s0Node);
child = s0Node;
}
buildTreeHelper(child, s.substring(1));
}
}
The time and space complexity are both O(n) where n is the number of characters of all words in the array. Due to ambiguous search, we have to search all paths in the worst case to get the final match. So trie does not improve the worst case time complexity compared with the brutal force word by word comparing.
Like above trie algo, the brutal force algo can also use string length and char difference count to early terminate the comparison. So I am a little confused how trie is useful at all. :( Any insight will be highly appreciated.
public class OneCharDifference {
public static void main(String[] args) {
System.out.println("Enter the String");
Scanner in = new Scanner(System.in);
String str = in.nextLine();
String[] arr = {"bana", "apple", "banaba", "bonanza", "bonamf"};
int count = 0;
for(int i=0; i<arr.length; i++) {
if(arr[i].length() == str.length()) {
for(int j=0; j <str.length(); j++) {
if(arr[i].charAt(j)!=str.charAt(i)) {
count++;
}
}
if(count == 1) {
System.out.println(arr[i]);
}
}
}
}
}
public class OneCharDifference {
public static void main(String[] args) {
System.out.println("Enter the String");
Scanner in = new Scanner(System.in);
String str = in.nextLine();
String[] arr = {"bana", "apple", "banaba", "bonanza", "bonamf"};
int count = 0;
for(int i=0; i<arr.length; i++) {
if(arr[i].length() == str.length()) {
for(int j=0; j <str.length(); j++) {
if(arr[i].charAt(j)!=str.charAt(i)) {
count++;
}
}
if(count == 1) {
System.out.println(arr[i]);
}
}
}
}
}
public class OneCharDifference {
public static void main(String[] args) {
String str = "banana";
String[] arr = {"bana", "apple", "banaba", "bonanza", "bonamf"};
int count = 0;
for(int i=0; i<arr.length; i++) {
if(arr[i].length() == str.length()) {
count = 0;
for(int j=0; j <str.length(); j++) {
if(arr[i].charAt(j)!=str.charAt(j)) {
count++;
}
}
if(count == 1) {
System.out.println(arr[i]);
}
}
}
}
}
public class OneCharDifference {
public static void main(String[] args) {
System.out.println("Enter the String");
Scanner in = new Scanner(System.in);
String str = in.nextLine();
String[] arr = {"bana", "apple", "banaba", "bonanza", "bonamf"};
int count = 0;
for(int i=0; i<arr.length; i++) {
if(arr[i].length() == str.length()) {
for(int j=0; j <str.length(); j++) {
if(arr[i].charAt(j)!=str.charAt(i)) {
count++;
}
}
if(count == 1) {
System.out.println(arr[i]);
}
}
}
}
}
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
public class OneCharacterDiff {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("bana");
list.add("apple");
list.add("bananb");
String testString = "banana";
System.out.println("Is one diff?? "+isOneDiff(list, testString));
}
private static Boolean isOneDiff(List<String> list, String testString) {
List<String> str = new ArrayList<>();
HashMap<String, String> map = new HashMap<>();
HashSet<Integer> hs = new HashSet<Integer>();
for(String s:list){
map.put(s,getSorted(s));
}
testString = getSorted(testString);
int c = 0;
int diff =0;
for(String s: list){
if(s.length()==testString.length()){
String m = map.get(s);
for(int i=0;i<m.length();i++){
if(m.charAt(i)!=testString.charAt(i)){
c++;
}
//hs.add(c);
}
if(c==1)
return true;
}
}
//if(hs.contains(1))
//return true;
//else
return false;
}
private static String getSorted(String s) {
char[] arr = s.toCharArray();
Arrays.sort(arr);
return new String(arr);
}
}
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
public class OneCharacterDiff {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("bana");
list.add("apple");
list.add("bananb");
String testString = "banana";
System.out.println("Is one diff?? "+isOneDiff(list, testString));
}
private static Boolean isOneDiff(List<String> list, String testString) {
List<String> str = new ArrayList<>();
HashMap<String, String> map = new HashMap<>();
HashSet<Integer> hs = new HashSet<Integer>();
for(String s:list){
map.put(s,getSorted(s));
}
testString = getSorted(testString);
int c = 0;
int diff =0;
for(String s: list){
if(s.length()==testString.length()){
String m = map.get(s);
for(int i=0;i<m.length();i++){
if(m.charAt(i)!=testString.charAt(i)){
c++;
}
//hs.add(c);
}
if(c==1)
return true;
}
}
//if(hs.contains(1))
//return true;
//else
return false;
}
private static String getSorted(String s) {
char[] arr = s.toCharArray();
Arrays.sort(arr);
return new String(arr);
}
}
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
public class OneCharacterDiff {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("bana");
list.add("apple");
list.add("bananb");
String testString = "banana";
System.out.println("Is one diff?? "+isOneDiff(list, testString));
}
private static Boolean isOneDiff(List<String> list, String testString) {
List<String> str = new ArrayList<>();
HashMap<String, String> map = new HashMap<>();
HashSet<Integer> hs = new HashSet<Integer>();
for(String s:list){
map.put(s,getSorted(s));
}
testString = getSorted(testString);
int c = 0;
int diff =0;
for(String s: list){
if(s.length()==testString.length()){
String m = map.get(s);
for(int i=0;i<m.length();i++){
if(m.charAt(i)!=testString.charAt(i)){
c++;
}
//hs.add(c);
}
if(c==1)
return true;
}
}
//if(hs.contains(1))
//return true;
//else
return false;
}
private static String getSorted(String s) {
char[] arr = s.toCharArray();
Arrays.sort(arr);
return new String(arr);
}
}
Can someone please tell me whats wrong with this simple c# solution ?
string[] arr = { "apple","banaga","orange"};
string test = "banana";
char[] a1;
char[] a2;
int count=0;
a2 = test.ToCharArray();
for (int i = 0; i < arr.Length; i++)
{
a1= arr[i].ToCharArray();
for (int j = 0; j < a1.Length; j++)
{
if (a1[j] != a2[j])
count++;
if (count > 1) break;
}
if (count == 0 || count == 1)
Console.WriteLine("TRUE");
count = 0;
}
in perl
my $string = "banana";
my @array = ('bana','apple','banaba','nonanza','banamf');
foreach my $str (@array) {
if (length($str) == length($string)) {
my $result = {};
for (0..length($str)){
if (substr($str,($_-1),1) eq substr($string,($_-1),1)) {
$result{'match'} += 1;
} else {
$result{'mismatch'} += 1;
}
}
if ($result{'mismatch'} == 1) {
print "found a match with one character difference at: $str\n";
}
}
}
my $string = "banana";
my @array = ('bana','apple','banaba','nonanza','banamf');
foreach my $str (@array) {
if (length($str) == length($string)) {
my $result = {};
for (0..length($str)){
if (substr($str,($_-1),1) eq substr($string,($_-1),1)) {
$result{'match'} += 1;
} else {
$result{'mismatch'} += 1;
}
}
if ($result{'mismatch'} == 1) {
print "found a match with one character difference at: $str\n";
}
}
}
my $string = "banana";
my @array = ('bana','apple','banaba','nonanza','banamf');
foreach my $str (@array) {
if (length($str) == length($string)) {
my $result = {};
for (0..length($str)){
if (substr($str,($_-1),1) eq substr($string,($_-1),1)) {
$result{'match'} += 1;
} else {
$result{'mismatch'} += 1;
}
}
if ($result{'mismatch'} == 1) {
print "found a match with one character difference at: $str\n";
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String s1 = "banana";
String[] a1 = {"nana", "baban", "banaba", "abfsdc", "bayana", "banxna"};
findmatch(s1, a1);
}
public static void findmatch(String s, String[] sa){
char[] chars = s.toCharArray();
for(int i = 0; i< sa.length;i++){
char[] s1 = sa[i].toCharArray();
int counter = 0;
if(chars.length == s1.length){
for(int k=0; k<chars.length || k<s1.length;){
if(chars[k] == (s1[k]))
k++;
else{
counter++;
k++;
}
}
}
if (counter == 1)
System.out.println(sa[i]);
}
}
boolean oneDiff(String s, String t) {
if(s.length() != t.length())
return false;
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) != t.charAt(i)) {
return s.substring(i+1).equals(t.substring(i+1));
}
}
return false;
}
boolean oneEditDiff(String s, String[] strs) {
if(strs == null || strs.length == 0)
return false;
for(String str : strs ) {
if(str.equals(s)) continue;
if(oneDiff(s, str)) return true;
}
return false;
}
public static void main(String[] args) {
Test test = new Test();
String[] strs = {"banana", "bana" , "banaa"};
System.out.println(test.oneEditDiff("banana", strs));
}
String banana="banana";
String[] findBanana = {"bana", "apple", "banaba", "bonanza", "banamf","bananaw"};
System.out.println("banana length: "+banana.length());
System.out.println("findBanana length: "+findBanana.length);
System.out.println("findBanana[0] value: "+findBanana[0]);
for(int i=0;i<findBanana.length;i++){
int count=0;
for(int j=0;j<findBanana[i].length();j++){
if (j>=banana.length()) continue;
if(banana.charAt(j)!=findBanana[i].charAt(j)){
count++;
}
}
if (count==1) System.out.println("Matching String is: "+findBanana[i]);
}
Hey All find my solution..!!
String banana="banana";
String[] findBanana = {"bana", "apple", "banaba", "bonanza", "banamf","bananaw"};
System.out.println("banana length: "+banana.length());
System.out.println("findBanana length: "+findBanana.length);
System.out.println("findBanana[0] value: "+findBanana[0]);
for(int i=0;i<findBanana.length;i++){
int count=0;
for(int j=0;j<findBanana[i].length();j++){
if (j>=banana.length()) continue;
if(banana.charAt(j)!=findBanana[i].charAt(j)){
count++;
}
}
if (count==1) System.out.println("Matching String is: "+findBanana[i]);
}
public class StringFinder {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input = "banana";
String[] arrayInput = {"bana", "apple", "banaba", "bonanza", "banamf"};
System.out.println(stringFind(input, arrayInput));
}
public static boolean stringFind(String str, String[] arrString){
int notMatch=0;
for(int i=0; i<arrString.length; i++){
int x = arrString[i].length();
if(x==str.length()){
char[] arr = arrString[i].toCharArray();
char[] inputStr = str.toCharArray();
for(int j =0; j<inputStr.length; j++){
if(inputStr[j]!=arr[j]){
notMatch++;
if(notMatch>1)
return false;
}
}
return true;
}
}
return false;
}
}
Python:
s = 'banana'
list1 = ['bana', 'apple', 'banaba', 'bonanza', 'banamf', 'banana']
def check(s,list1):
if len(s) == 0 or len(list1) == 0:
return False
list2 = []
for items in list1:
if len(s) == len(items):
count = 0
for i in range(0,len(s)):
if s[i] != items[i]:
count += 1
if count <= 1:
list2.append(items)
return list2
list2 = check(s,list1)
if len(list2) > 0:
print "True"
print list2
given
$g = "banana"; # given string
@ary = qw(
bana apple banaba nonanza banamf
anana banan ananas banaa bnana
);
if strings have to be of equal length:
print $_,$/ for grep {
1 == grep !/0/, unpack "C*", $g ^ $_
if length $g == length $_
} @ary;
__END__
banaba
including strings which have one char missing somewhere:
print $_,$/ for grep {
my ($lg, $lc) = map { length $_ } $g, $_;
my $ret;
if ($lg - $lc == 1) {
my $re = join'.?','',(split//,$_),'';
$ret = $g =~ /$re/;
} elsif ($lg == $lc) {
$ret = (1 == grep !/0/, unpack "C*", $g ^ $_);
}
$ret;
} @ary;
__END__
banana
anana
banan
banaa
bnana
given
$g = "banana";
@ary = qw(
bana apple banaba nonanza banamf
anana banan ananas banaa bnana
);
if strings have to be of equal length:
print $_,$/ for grep {
1 == grep !/0/, unpack "C*", $g ^ $_
if length $g == length $_
} @ary;
__END__
banaba
including strings which have one char missing somewhere:
print $_,$/ for grep {
my ($lg, $lc) = map { length $_ } $g, $_;
my $ret;
if ($lg - $lc == 1) {
my $re = join'.?','',(split//,$_),'';
$ret = $g =~ /$re/;
} elsif ($lg == $lc) {
$ret = (1 == grep !/0/, unpack "C*", $g ^ $_);
}
$ret;
} @ary;
__END__
banana
anana
banan
banaa
bnana
if strings have to be of the same length:
# $g is given string, @ary is array of strings
print 0 < grep {
1 == grep !/0/, unpack "C*", $g ^ $_ if length $g == length $_
} @ary;
if strings 1 char shorter or larger are allowed:
print 0 < grep {
my ($lg, $lc, $ret) = map { length $_ } $g, $_;
if (abs (my $d = $lg - $lc) == 1) {
my $re = join '.?', '', (split//,$d > 0 ? $_: $g), '';
$ret = ($d > 0 ? $g : $_) =~ /$re/;
} elsif ($lg == $lc) {
$ret = (1 == grep !/0/, unpack "C*", $g ^ $_)
}
$ret
} @ary;
I don't see an efficient solution other than looking iteratively for any character in any word until I find the first match:
using static System.Console;
using static System.Math;
using System.Collections.Generic;
using System.Linq;
using System;
namespace Coding {
public static class CareerCup {
public static string Run(string[] args) {
return HasSimilarWords(args[0], args.Skip(1).ToList()).ToString();
}
// return only the words in the array that differ from the input
// words by one character
public static bool HasSimilarWords(string word, IList<string> words) {
return words.Any(word.IsSimilar);
}
public static bool IsSimilar(this string a, string b) {
if(a.Length != b.Length) return false;
var wrong = false;
for(var i = 0; i < a.Length; i++) {
if(a[i] != b[i]) {
if(wrong) return false;
else wrong = true;
}
}
return true;
}
}
}
/*program to find string with one difference character */
#define ROW 5
#define COLUMN 20
#include<stdio.h>
#include<string.h>
int main()
{
char str[ROW][COLUMN],check[COLUMN];
int i,j,x,y,a,k;
printf("Enter 5 words:\n");
while(i<ROW) //while loop to enter elements in the string array.
{
scanf("%s",str[i++]);
} //end of whil loop.
printf("Enter string to check:\n");
scanf("%s",check);
i=0;
printf("check string : %s\n",check);
x=strlen(check);
i=0;
k=0;
while(k < 5) //begining of main while loop.
{
y=strlen(str[k]);
if(x==y)
{
if (strcmp(check,str[k])==0) //begining of inner if.
{
// printf("string matched:%s\n",str[k]);
} //end of inner if.
else // begining of inner else
{
a=0;
for(j=0;j<x;j++) //for loop for going character wise match of each string.
{
if(check[j]!= str[k][j])
{
a++;
}
} // end of for loop.
if(a==1)
{
printf("Element found:%s\n",str[k]);
}
} //end of inner else.
} //end of outter if.
k++;
} // end of main while loop.
return 0;
} // end of main().
#include <iostream>
#include <vector>
using namespace std;
// To execute C++, please define "int main()"
bool isOneCharDiffStringExist(vector<string> list, string s)
{
int length = (int)list.size();
if(length == 0 || s.size() ==0)
return false;
for(int i=0;i<length;i++)
{
if(list[i].size()!=s.size())
continue;
bool oneCharDiffFound = false;
for(int j =0;j<(int)list[i].size();j++)
{
if(list[i][j] != s[j] )
{
if(!oneCharDiffFound)
oneCharDiffFound = true;
else
{
oneCharDiffFound = false;
break;
}
}
}
if(oneCharDiffFound)
return true;
}
return false;
}
int main() {
vector<string> list;
list.push_back("bana");
list.push_back("apple");
list.push_back("banacb");
list.push_back("bonanza");
list.push_back("banamf");
cout<<isOneCharDiffStringExist(list,"banana");
return 0;
}
I think this code will not work for given string "banana"-"abnaba",even though there is difference of one character only.Please give suggestions.
@nanhi: I see a difference of 3 characters...
@OP: This won't work when there is a word of different sizes but still have a one character difference, take this example:
banana --> bananaa
There is a 1 character difference only, but this function will skip it as the sizes aren't equal.
@nanhi: I count 3 differences in the above. They're most likely counting a difference as str[i] != str1[i]. In your above example str[0] doesn't match, str[1] doesn't match, and str[4] doesn't match.
@OP:
I don't think your function works when the strings are different sizes, yet still only differ by 1 character, take the following example:
banana --> bananaa
There is only 1 character difference (the last char), but it will not be found because it will get skipped due to the size difference.
We no need to handle the scenario of banana --> bananas.
The length of the strings needs to matcha and one character changed between the strings.
Same concept as LCS(longest common sub sequence):
#include <stdio.h>
int max = -1;
int maximum(int a, int b)
{
return a>b?a:b;
}
int foo(char *target, char *a[10], int i, int j, int size, int cost)
{
if (i >= size) {
if (cost+abs(strlen(a[i])-strlen(target)) > 1) {
return foo(target, a, i+1, 0, size, 0);
}
printf("%s\n", a[i]);
return 0;
}
if (j >= strlen(a[i])) {
if (cost+abs(strlen(a[i])-strlen(target)) > 1) {
return foo(target, a, i+1, 0, size, 0);
}
printf("%s\n", a[i]);
return 0;
}
if (a[i][j] == target[j]) {
return foo(target, a, i, j+1, size, cost);
} else {
return foo(target, a, i, j+1, size, cost + 1);
}
}
int main(void) {
char *s = {"banana"};
char *a[10] = {"bana", "apple", "sanana", "banaba", "bonanza", "banamf"};
printf("%d\n", foo(s, a, 0, 0, 5, 0));
return 0;
}
We can put all the words in hashset, and then for every character in input word, try to change it and lookup in hashset. overall complexity O(ALPH * N), where N is the length of word and ALPH is the size of alphabet. Usually we skip constants in big O notation, so the complexity O(N)
- Darkhan.Imangaliev October 06, 2015