Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
didn't work for this input ?
{"dog","done","good","go","gogo","gold","golf","why","which","while","zebra", "duck","dot"}
Ah, I didn't test it properly. But the problem is by the commentary, that says:
"bar", "bartender" situation - unclear instructions from OP
There shouldn't be return.
There should be following:
result.insert(pair<string, string>(prefix, prefix));
But I believe that the overall idea is correct no matter the small details.
This was my first idea too, elegant and simple. It does take, however extra O(n*m) space, where n is the number of words and m is the average word length. And the time complexity is O(n*m) to build the trie, plus O(n*m) to produce the result.
All in all, O(n*m) time with O(n*m) space.
There is another solution possible, sorting the array first in O((n*m)logn) and then comparing each word with the next (also keeping what the last common prefix was), this step will require an extra O(n*m) time. This solution overall complexity is O(1) space and O(n*m log n) time.
And this is it:
static String[] uniqueprefix(String[] words){
String[] prefix = new String[words.length];
Arrays.sort(words);
String prevPrefix = "";
String nextPrefix = "";
for(int i = 0; i < words.length; i++){
String current = words[i];
if(i < words.length-1){
String next = words[i+1];
prevPrefix = nextPrefix;
int idx = 0;
while(idx < current.length() && current.charAt(idx) == next.charAt(idx)) idx++;
nextPrefix = idx == 0 ? "" : current.substring(0, idx);
String elected;
if(prevPrefix.length() > nextPrefix.length())
elected = prevPrefix;
else
elected = nextPrefix;
if(elected.length() == current.length()){
prefix[i] = "";
nextPrefix = nextPrefix.substring(0, nextPrefix.length()-1);
}
else
prefix[i] = elected + current.charAt(elected.length());
}
else{
prefix[i] = nextPrefix + current.charAt(nextPrefix.length());
}
}
return prefix;
}
build a trie of all the words. later on go over all the input words you got, and for each word save the node after last "split node" you had in the trie for that word. this "split node" +1 is the prefix you need to find the word later
class Solution
{
public:
vector<string> shortprefix(vector<string> input)
{
sort(input.begin(),input.end());
int l=input.size();
vector<string> ans(l," ");
for (int i=0;i<l;++i)
{
int left=0,right=0;
if (i>0)
{
int l1=min(input[i].length(),input[i-1].length());
while (left<l1 && input[i][left]==input[i-1][left]) left++;
}
if (i<l-1)
{
int l2=min(input[i].length(),input[i+1].length());
while (right<l2 && input[i][right]==input[i+1][right]) right++;
}
int x=max(left,right);
ans[i]=input[i].substr(0,x+1);
if (x==input[i].length()) ans[i]="";
}
return ans;
}
};
Here is my prefix tree implementation.
time complexity and space complexity are O(n) where n is sum of characters in all words.
Note that behaviour of createPrefix for word that wasn't in initial array of strings is undefined.
And also statement of problem is somewhat ambiguous. I assume that in examples prefix for "dog" should be "dog" itself, and the same for "dot" and "bear". If it should be empty string then it's possible to create wrapper that will compare result of findPrefix and word itself.
import java.util.LinkedList;
import java.util.ListIterator;
class PrefixTree {
private final char value;
private int count;
private LinkedList <PrefixTree> descendants = new LinkedList <PrefixTree> ();
public PrefixTree (String[] strs) {
this.value = '\0';
count = 0;
for (String str : strs)
this.addWord (str);
}
private PrefixTree (char value) {
this.value = value;
count = 1;
}
private void updateDescendants (char[] str, int i) {
if (i < 0 || i >= str.length)
return;
PrefixTree ptd = addDescendant (str[i]);
ptd.updateDescendants (str, i +1);
}
private PrefixTree addDescendant (char descendantch) {
PrefixTree descendant = new PrefixTree (descendantch);
ListIterator <PrefixTree> it = this.descendants.listIterator();
while (it.hasNext()) {
PrefixTree ptd = it.next();
if (ptd.value < descendant.value)
continue;
if (ptd.value > descendant.value) {
it.set (descendant);
it.add (ptd);
return descendant;
}
if (ptd.value == descendant.value) {
ptd.count++;
return ptd;
}
}
this.descendants.add (descendant);
return descendant;
}
private void createPrefix (StringBuilder sb, char[] str, int i) {
if (i < 0 || i >= str.length)
return;
ListIterator <PrefixTree> it = this.descendants.listIterator();
while (it.hasNext()) {
PrefixTree ptd = it.next();
if (ptd.value < str[i])
continue;
if (ptd.value > str[i])
throw new RuntimeException ("Word is not in the PrefixTree");
if (ptd.value == str[i]) {
sb.append (ptd.value);
if (ptd.count == 1) return;
ptd.createPrefix (sb, str, i +1);
return;
}
}
throw new RuntimeException ("Word is not in the PrefixTree");
}
private void addWord (String str) {
this.updateDescendants (str.toCharArray(), 0);
}
public String findPrefix (String str) {
StringBuilder sb = new StringBuilder();
this.createPrefix (sb, str.toCharArray(), 0);
return sb.toString();
}
public static void main (String[] args) {
PrefixTree pt = new PrefixTree(args);
for (String str : args)
System.out.println (pt.findPrefix (str));
}
}
use trie with count
#include <iostream>
#include <string>
using namespace std;
struct node
{
char key;
node *child[26];
int count=0;
};
class trie
{
public:
node *root;
trie()
{
root=new node;
}
void insert(string st)
{
node *cur=root;
for (int i=0;i<st.length();++i)
{
if (!cur->child[st[i]-'a'])
{
node *tmp=new node;
cur->child[st[i]-'a']=tmp;
}
(cur->child[st[i]-'a']->count)++;
cur=cur->child[st[i]-'a'];
}
}
bool search(string st)
{
node *cur=root;
for (int i=0;i<st.length();++i)
{
if (!cur->child[st[i]-'a']) return false;
else cur=cur->child[st[i]-'a'];
}
return true;
}
void print(string prefix, node* &root)
{
int i=0;
while (i<26)
{
if (root->child[i] && root->child[i]->count==1)
{
prefix.push_back(i+'a');
cout<<prefix<<endl;
prefix.pop_back();
}
else if (root->child[i] && root->child[i]->count!=1)
{
prefix.push_back(i+'a');
print(prefix,root->child[i]);
prefix.pop_back();
}
i++;
}
}
};
int main()
{
trie test;
test.insert("zebra");
test.insert("dog");
test.insert("duck");
test.insert("dot");
test.insert("bearc");
test.insert("bear");
test.print("",test.root);
cout<<endl;
cout<<test.root->child[3]->child[14]->child[6]->count<<endl;
return 0;
}
My approach to this would be
input: ["zebra", "dog", "duck",”dot”]
1. Assume we are dealing with simple characters, maintain a character counter and increment the counter on occurrence of that letter in all the words
example - Using the Hashmaps, we can have z:1,e:1,b:1,r:1,a:1,d:3...
2. Compare the current word and create the prefix in a by appending the letters until you find the letter with 1 occurrence.
With that we the output would be z,dog,du,dot
Also won't work for ["zebra", "bear", "duck", "bearcat"]. Doesn't take into account the positions of characters, simply count won't solve it for you.
this is very easy :
this is O(n) solution
a- scan all the words add the first letter to a map , this will tell you the letters you need to process
b- scan the list for each letter collect the words for that letter
c- for the collected words start add them to a temp map
c-1: if the collected words is more than 1 start by adding using the first 2 letters
c-2: if you couldn't add all the words using first 2 letters retry using 3 letters and so on
d- After all you words added to temp map Add them to the main map
e: continue till you finish your letter map
here it is :
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
void shortestPrefixMap(){
string wordList[] ={"dog","done","good","go","gogo","gold","golf","why","which","while","zebra", "duck","dot"};
map<char,int> lettersMap ;
int len = sizeof(wordList)/sizeof(wordList[0]);
for(int i=0;i<len;i++){
char firstWordLetter = wordList[i].at(0);
if(lettersMap.count(firstWordLetter)>0){
lettersMap[firstWordLetter]+=1;
}
else{
lettersMap[firstWordLetter]=1;
}
}
map<string,string> wordsMap;
map<string,string> MainMap;
vector<string> words;
for(auto it : lettersMap){
words.clear();
wordsMap.clear();
for(auto word : wordList){
if(word.at(0)!=it.first) continue;
words.push_back(word);
}
// for the collected words start the prefix
if(words.size()==1){
// add it to the main
MainMap[words[0]]=words[0].at(0);
}
else {
// prefix
int substrignEnd=1;
int count=0;
while(count<it.second){
string key = words[count].substr(0,substrignEnd);
while(wordsMap.count(key)>0){
substrignEnd+=1;
key = words[count].substr(0,substrignEnd);
}
wordsMap[key]=words[count];
substrignEnd=1;
count++;
}
// everything done add them to the main map
for(auto it : wordsMap){
MainMap[it.second]=it.first;
}
}
}
for(auto it : MainMap ){
cout<<it.first<<"=>"<<it.second<<endl;
}
}
int main(int argc, const char * argv[]) {
shortestPrefixMap();
return 0;
}
Dr. H the solution looks very complicated what are you trying to do here..
What's wrong with a trie
#include<iostream>
struct Carrier
{
string s;
bool Valid;
Carrier(string a="",bool b=true){s=a;Valid=b;}
};
void printlf(map<string,string> a)
{
map<string,string>::iterator it;cout<<"\n hashMap\n";
for(it=a.begin();it!=a.end();++it)cout<<"\n\t"<<it->first<<"-->"<<it->second ;
}
void print(map<string,Carrier> a)
{
map<string,Carrier>::iterator it;cout<<"\n hashMap\n";
for(it=a.begin();it!=a.end();++it)cout<<"\n\t"<<it->first<<"-->"<<it->second.s <<"\t\t\t Valid:"<<it->second.Valid;
}
void operat(map<string,Carrier> & a,string c,string ts)
{
string n1,n2;
map<string,Carrier>::iterator it;
it=a.find(c);unsigned int ii;
{
Carrier k=it->second;
for(ii=0;ii<ts.size() && ii<k.s.size() && ts[ii]==k.s[ii];n1+=ts[ii],n2+=ts[ii],ii++);
if(ii>=ts.size()){Carrier we;
n2+=k.s[ii];
a[n1]=we;
a[n2]=k.s;}
else if(ii>=k.s.size()){Carrier we;n1+=ts[ii];a[n1]=ts;a[n2]=we;}
else {n1+=ts[ii];n2+=k.s[ii];a[n1]=ts;a[n2]=k.s; }
it=a.find(c);
it->second.Valid=false;
}
}
void problem(string a,string b)
{
}
int main()
{
string a[]={"zebra", "dog", "duck", "dove","bear","bearcat"};
map<string,Carrier> mymap;
map<string,string> lf;
map<string,Carrier>::iterator it;
for(int ii=0;ii<6;ii++)
{ string c;
c+=(a[ii][0]);
if(mymap.find(c)==mymap.end())
{Carrier k(a[ii]);mymap[c]=k;
}
else
{operat(mymap,c,a[ii]);
}
}
print(mymap);
for(it=mymap.begin();it!=mymap.end();++it)if(it->second.Valid)lf[it->second.s]=it->first;
printlf(lf);
}
Hi my solution for that problem. I was looking for something concise in the code. So you don't have time during 45 min interview implement large portion of the code. You need to be concise.
class ShortPrefixer {
public static void main(String args[]) {
String[] input = {"zebra", "dog", "duck", "dot"};
generateShortcuts(input);
String[] input2 = {"zebra", "dog", "duck", "dove"};
generateShortcuts(input2);
String[] input3 = {"bearcat", "bear"};
generateShortcuts(input3);
}
// returns len of the shared path between two words in input array. Compared words are taken from pos x and y.
static int getSharedLen(String[] input, int x, int y){
if ( y < 0 ) return 0;
if ( y>= input.length ) return 0;
String w1 = input[x];
String w2 = input[y];
int pos = 0;
while(pos<w1.length() && pos < w2.length() && w1.charAt(pos) == w2.charAt(pos)) pos++;
return pos;
}
static void generateShortcuts(String[] input){
Arrays.sort(input);
for(int x=0;x<input.length;x++){
int prefixLen = (int) Math.max(getSharedLen(input, x,x+1), getSharedLen(input, x,x-1)) +1;
if (prefixLen<=input[x].length()) {
System.out.println(input[x] + ":: " +input[x].substring(0, prefixLen));
}else{
System.out.println(input[x] + "::"); //no possible unique prefix
}
}
}
}
O(n): hand-made hashmap for quick analysis of each starting letter-
void GetPrefixes(std::list<std::string>& strList, std::list<std::string>& prefixList)
{
std::list<std::string> wordList[26];
for(std::list<std::string>::iterator i = strList.begin(); i != strList.end(); i++)
{
char c = i->at(0);
wordList[c - 'a'].push_back(*i);
}
for(std::list<std::string>::iterator i = strList.begin(); i != strList.end(); i++)
{
char c = i->at(0);
std::list<std::string>& words = wordList[c - 'a'];
std::string str;
str.append(1, c);
if(words.size() <= 1)
{
// this is the only word of this letter! we're done
prefixList.push_back(str);
}
else
{
unsigned int letter = 1;
str.append(1, i->at(letter));
// append a letter at a time that can be compared against the mini-list
while(letter < i->size())
{
bool foundIt = false;
for(std::list<std::string>::iterator j = words.begin(); j != words.end(); j++)
{
// make sure we don't compare against ourselves!
if(j->find(str) == 0 && (*j != *i))
{
foundIt = true;
break;
}
}
// if we found a match, keep getting more specific, otherwise: we're done
if(foundIt)
{
letter++;
if(letter >= i->size())
{
prefixList.push_back(str);
break;
}
else
{
str.append(1, i->at(letter));
}
}
else
{
prefixList.push_back(str);
break;
}
}
}
}
}
Simply use a prefix tree to implement and here is an C++ code
[code]
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<climits>
using namespace std;
struct node{
int count;
map<char,node*>child;
node():count(0){;}
};
void insert(node*p,string s){
p->count++;
if(s.empty())return;
if(p->child.count(s[0])==0)
p->child[s[0]]=new node();
insert(p->child[s[0]],s.substr(1,s.size()-1));
}
string query(node*root,string s){
node*p=root;
for(int i=0;i<s.size();i++){
p=p->child[s[i]];
if(p->count==1)
return s.substr(0,i+1);
}
return s;
}
int main(){
vector<string>v;
v.push_back("bearcat");
v.push_back("bear");
node*root=new node();
for(int i=0;i<v.size();i++)
insert(root,v[i]);
for(int i=0;i<v.size();i++)
cout<<v[i]<<":"<<query(root,v[i])<<endl;
return 0;
}
[/code]
Simply use a prefix tree to implement and here is an C++ code
[code]
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<climits>
using namespace std;
struct node{
int count;
map<char,node*>child;
node():count(0){;}
};
void insert(node*p,string s){
p->count++;
if(s.empty())return;
if(p->child.count(s[0])==0)
p->child[s[0]]=new node();
insert(p->child[s[0]],s.substr(1,s.size()-1));
}
string query(node*root,string s){
node*p=root;
for(int i=0;i<s.size();i++){
p=p->child[s[i]];
if(p->count==1)
return s.substr(0,i+1);
}
return s;
}
int main(){
vector<string>v;
v.push_back("bearcat");
v.push_back("bear");
node*root=new node();
for(int i=0;i<v.size();i++)
insert(root,v[i]);
for(int i=0;i<v.size();i++)
cout<<v[i]<<":"<<query(root,v[i])<<endl;
return 0;
}
[/code]
Using tree.
#include <vector>
#include <string>
#include <map>
#include <memory>
#include <iostream>
using namespace std;
class GraphNode {
public:
map<char, shared_ptr<GraphNode>> children;
string value;
bool isLeaf;
GraphNode() {isLeaf = false;}
};
void addWord(shared_ptr<GraphNode> g, string word)
{
auto child = g->children[word[0]];
if(child == nullptr) {
child = g->children[word[0]] = make_shared<GraphNode>();
child->value = word.substr(1);
if(child->value.size() == 0) {
child->isLeaf = true;
}
} else {
if (child->value.size() > 0) {
addWord(child, child->value);
child->value = string();
}
addWord(child, word.substr(1));
}
}
void printGraph(shared_ptr<GraphNode> g, vector<char> sofar)
{
if(g->isLeaf || g->children.size() == 0) {
string abbrev;
for(auto n : sofar) {
abbrev.push_back(n);
}
cout << abbrev << ": " << abbrev << g->value << endl;
}
for( auto it = g->children.begin(); it != g->children.end(); ++it ) {
auto ch = it->first;
auto child = it->second;
auto v = sofar;
v.push_back(ch);
printGraph(child, v);
}
}
int main()
{
auto root = make_shared<GraphNode>();
addWord(root,"dog");
addWord(root,"duck");
addWord(root, "zebra");
addWord(root, "dot");
addWord(root, "dogma");
printGraph(root, vector<char>());
return 0;
}
//simple o(nlogn) solution and o(n) space
private static Map<String,String> getPrefixes(String [] str) {
Map<String,String> word2PrefixMap = new HashMap<String, String>();
int [] lcps = new int[str.length];
Arrays.sort(str);
for(int i =0;i<str.length-1;i++) {
int lcp = lcp(str[i],str[i+1]);
lcps[i] = Math.max(lcps[i], lcp);
lcps[i+1] = Math.max(lcps[i+1], lcp);
}
for (int i = 0; i < lcps.length; i++) {
String prefix;
if(lcps[i] == str[i].length()) {
prefix = "";
}
else {
prefix = str[i].substring(0,lcps[i]+1);
}
word2PrefixMap.put(str[i], prefix);
}
return word2PrefixMap;
}
private static int lcp(String str1, String str2) {
int j = -1;
for( int i= 0;i<Math.min(str1.length(),str2.length());i++) {
if(str1.charAt(i)!=str2.charAt(i)) break;
j = i;
}
return j+1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String [] words = new String[] {"zebra", "dog", "duck","dot"};
// String [] words = new String[] {"bearcat", "bear"};
System.out.println(getPrefixes(words));
}
In the structure of my PatriciaTree, it has following parameters:
char c, indicate the char the node has.
HashMap<Character, PatriciaTree> children, indicate the children the node has.
String leftString, this a bit difficult to explain. So let me raise an example. If root only has a word "dog". So the structure would be like:
.root.......
..\.........
...d(og)....
But not:
.root.......
..\.........
...d........
....\.......
.....o......
......\.....
.......g....
So, in this case, I use the leftString to store the string after 'd', which is 'og'. And I call the node d(og) string leaf. Because it is a leaf, and it needs to indicate what string it still has.
I define 4 types of nodes in patricia tree:
STATE_ROOT, the root the patricia tree.
STATE_STRINGLEAF, it is a leaf, and it has left string in it. Like the example I showed above.
STATE_LEAF, it is a leaf, and it doesn't has left string.
For example, the 'g' and 't' nodes are both LEAF node, but not string leaf node.
.root.........
..\...........
...d..........
....\.........
.....o........
..../.\.......
...g...t......
STATE_MIDDLE, in the above case, the 'd' and 'o' are middle nodes.
In the following code. I demonstrate how to build a patricia tree, and the method to find if a word exists in a patricia tree.
import java.util.HashMap;
public class PatriciaTree {
public static final int STATE_ROOT = 0;
public static final int STATE_LEAF = 1;
public static final int STATE_STRINGLEAF = 2;
public static final int STATE_MIDDLE = 3;
char c;
HashMap<Character, PatriciaTree> children;
int state; //0 is root, 1 is leaf, 2 is leaf with string, 3 is middle
String leftString; //if the node is leaf with string, it has a rest word
PatriciaTree parent;
//store word into this PatriciaTree, word starts from pos
public boolean addNode(String word, int pos, PatriciaTree parent){
if(word==null||pos>=word.length()){
return false;
}
PatriciaTree child;
if(state==STATE_ROOT||state==STATE_MIDDLE){
//if it is root, then find if it children have tree with character pos[0]
child = children.get(word.charAt(pos));
if(child==null){ //it doesn't has word.charAt[pos], then create tree under it.
child = new PatriciaTree(word, pos, this);
children.put(word.charAt(pos), child);
return true;
}
return child.addNode(word, pos+1, this); //it has char, then create tree under its child.
}
if(state==STATE_LEAF){
//now it is leaf, and there are still chars, then just change it to a STRINGLEAF
this.state = STATE_STRINGLEAF;
this.leftString = word.substring(pos, word.length()-1);
return true;
}
if(state==STATE_STRINGLEAF){
if(word.charAt(pos)!=leftString.charAt(0)){
//1st char of leftString doesn't match word[pos], so create the tree under it.
//And create leftString as its subtree.
child = new PatriciaTree(word, pos, this);
children.put(word.charAt(pos), child);
child = new PatriciaTree(leftString, 0, this);
children.put(leftString.charAt(0), child);
this.state = STATE_MIDDLE;
return true;
}
//1st char of leftString match word[pos], so break the stringleaf into middle,
//and create its child with char of the 1st leftString
this.state = STATE_MIDDLE;
child = new PatriciaTree(leftString, 0, this);
children.put(leftString.charAt(0), child);
this.leftString = "";
child.addNode(word, pos+1, child);
return true;
}
return false;
}
public boolean findString(String word, int pos){
if(pos>=word.length()){
if(this.state==STATE_MIDDLE){
return false; //is in the middle, is not counted as found.
}
if(this.state==STATE_LEAF){
return true; //return true if this is leaf
}
return false;
}
PatriciaTree child;
if(this.state==STATE_ROOT||this.state==STATE_MIDDLE){
child = this.children.get(word.charAt(pos));
return child==null?false:child.findString(word, pos+1);
}
if(this.state==STATE_LEAF){
return false; //the word is larger than the leaf string
}
if(this.state==STATE_STRINGLEAF){
String strInWord = word.substring(pos, word.length());
if(leftString.equals(strInWord)){
return true;
}
}
return false;
}
public PatriciaTree(){
this.children = new HashMap<Character, PatriciaTree>();
}
public PatriciaTree(String word, int pos, PatriciaTree parent){
this.c = word.charAt(pos);
this.parent = parent;
this.state = STATE_LEAF;
this.children = new HashMap<Character, PatriciaTree>();
if(pos<word.length()-1){
this.state = STATE_STRINGLEAF;
this.leftString = word.substring(pos+1, word.length());
}
}
public static void main(String[] args) {
PatriciaTree root = new PatriciaTree();
root.state = STATE_ROOT;
String[] words = {"zebra", "zero", "dog", "dot", "ducks", "duh", "ducky"};
for(int i=0;i<words.length;i++){
root.addNode(words[i], 0, root);
}
System.out.println(root.findString("dogg", 0));
}
}
One more approach using string array
#include<iostream>
#include<map>
using namespace std;
map<string,string> m;
int main()
{
string str[]={"zebra", "zero", "dog", "dot", "ducks", "duh", "ducky"};//{"dog","done","good","go","gogo","gold","golf","why","which","while","zebra", "duck","dot"};
int n=sizeof(str)/sizeof(str[0]);
sort(str,str + n);
for(int i=0;i<n;i++)
cout<<str[i]<<" ";
for(int i=0;i<n;i++)
m[str[i]]="";
int j=0;
for(int i=0;i<n;i++)
{
j=0;
for(j=0;j<str[i].length();j++)
{
if(i<n-1 && j<str[i+1].length() && str[i][j]==str[i+1][j])
{
if(j>=m[str[i]].length())
m[str[i]]+=str[i][j];
m[str[i+1]]+=str[i+1][j];
}
else{
j=m[str[i]].length();
break;
}
}
m[str[i]]+=str[i][j];
}
for(int i=0;i<n;i++)
{
cout<<"\n"<<str[i]<<" --- "<<m[str[i]];
}
return 0;
}
Java Implementation Using Trie idea.
/**
* input: ["zebra", "dog", "duck", "dot", "key", "keyVAlue"]
* output: {zebra: z, dog: dog, duck: du, dot: dot, key: "", keyValue: keyV}
**/
public class ShortestPrefixRepresent {
private TrieNode root = new TrieNode();
public ShortestPrefixRepresent(String[] array) {
for (String item : array) {
putIntoTrie(item);
}
}
public String getShortestPrefix(String target) {
StringBuffer res = new StringBuffer("");
TrieNode p = root;
for (int i = 0; i < target.length(); i++) {
res.append(target.charAt(i));
if (p.subNodes[target.charAt(i)] == null) {
return "";
} else {
if (p.subNodes[target.charAt(i)].count == 1) {
return res.toString();
}
}
p = p.subNodes[target.charAt(i)];
}
return "";
}
private void putIntoTrie(String item) {
TrieNode p = root;
for (int i = 0; i < item.length(); i++){
if (p.subNodes[item.charAt(i)] == null) {
p.subNodes[item.charAt(i)] = new TrieNode();
} else {
p.subNodes[item.charAt(i)].count += 1;
}
p = p.subNodes[item.charAt(i)];
}
}
public static void main(String[] args) {
String[] array = {"zebra", "dog", "duck", "dot", "key", "keyVAlue"};
ShortestPrefixRepresent code = new ShortestPrefixRepresent(array);
for (String item : array) {
System.out.println(item + ": " + code.getShortestPrefix(item));
}
}
}
class TrieNode{
int count = 1;
TrieNode[] subNodes = new TrieNode[256];
}
Two efficient methods:
a. Using radix sort (From front to back) : Time complexity is O(l) where l is sum of length of all strings.
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int n = Integer.parseInt(br.readLine());
ArrayList<String> words = new ArrayList<String>();
for (int i = 0; i < n; ++i) {
words.add(br.readLine());
}
ArrayList<String> result = new ArrayList<String>();
dfs(words, result, 0);
for (int i = 0; i < result.size(); ++i) {
out.println(result.get(i));
}
out.flush();
out.close();
System.exit(0);
}
private static void dfs(ArrayList<String> words, ArrayList<String> result, int index) {
if (words == null || words.size() == 0)
return;
else if (words.size() == 1) {
result.add(words.get(0).substring(0, index));
return;
}
else {
HashMap<Character, ArrayList<String>> buckets = new HashMap<Character, ArrayList<String>>();
for (int i = 0; i < words.size(); ++i) {
String word = words.get(i);
if (word.length() == index)
throw new RuntimeException("No unique prefixes");
char ch = word.charAt(index);
ArrayList<String> list = null;
if (!buckets.containsKey(ch)) {
list = new ArrayList<String>();
buckets.put(ch, list);
}
else {
list = buckets.get(ch);
}
list.add(word);
}
Set<Character> keys = buckets.keySet();
for (Character key:keys) {
dfs(buckets.get(key), result, index+1);
}
}
}
}
b. Using Trie : Maximum time complexity O(l) where l is sum of length of all strings.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int n = Integer.parseInt(br.readLine());
ArrayList<String> words = new ArrayList<String>();
for (int i = 0; i < n; ++i) {
words.add(br.readLine());
}
ArrayList<String> result = uniquePrefixes(words);
if (result != null) {
for (int i = 0; i < n; ++i) {
out.println(result.get(i));
}
}
out.flush();
out.close();
System.exit(0);
}
private static ArrayList<String> uniquePrefixes(ArrayList<String> words) {
int n = words.size();
TrieNode root = new TrieNode();
insert(root, words);
ArrayList<String> result = populateUniquePrefixes(root, words);
return result;
}
private static void insert(TrieNode root, ArrayList<String> words) {
if (root == null) {
return;
}
else {
for (int i = 0; i < words.size(); ++i) {
TrieNode current = root;
String word = words.get(i);
for (int j = 0; j < word.length(); ++j) {
char ch = word.charAt(j);
if (current.children.containsKey(ch)) {
TrieNode next = current.children.get(ch);
next.count = next.count+1;
current = next;
}
else {
TrieNode newNode = new TrieNode(ch, 1);
current.children.put(ch, newNode);
current = newNode;
}
}
}
}
}
private static ArrayList<String> populateUniquePrefixes(TrieNode root, ArrayList<String> words) {
ArrayList<String> result = new ArrayList<String>();
int n = words.size();
for (int i = 0; i < n; ++i) {
String word = words.get(i);
TrieNode current = root;
StringBuffer sb = new StringBuffer();
int j = 0;
for (; j < word.length(); ++j) {
char ch = word.charAt(j);
int count = current.children.get(ch).count;
if (count == 1) {
sb.append(ch);
result.add(sb.toString());
break;
}
else {
sb.append(ch);
current = current.children.get(ch);
}
}
if (j == word.length()) {
throw new RuntimeException("No unique prefixes");
}
}
return result;
}
private static class TrieNode {
public char val;
public int count = 0;
public HashMap<Character, TrieNode> children = null;
public TrieNode() {
children = new HashMap<Character, TrieNode>();
}
public TrieNode(char val, int count) {
children = new HashMap<Character, TrieNode>();
this.val = val;
this.count = count;
}
}
}
//Smallest and easiest solution. Enjoy..
public ArrayList<String> shortestUniquepath(ArrayList<String> a){
ArrayList<String> result = new ArrayList<>();
HashMap<String, Integer> hm = new HashMap<>();
for(int i = 0;i<a.size();i++){
String currStr = a.get(i);
StringBuilder sb = new StringBuilder();
for(int j = 0;j<currStr.length();j++){
sb.append(currStr.charAt(j));
if(hm.containsKey(sb.toString())){
hm.put(sb.toString(), hm.get(sb.toString()) + 1);
}else{
hm.put(sb.toString(), 1);
}
}
}
for(int i = 0;i<a.size();i++){
String currStr = a.get(i);
StringBuilder sb = new StringBuilder();
for(int j = 0;j<currStr.length();j++){
sb.append(currStr.charAt(j));
if(hm.get(sb.toString()) == 1){
result.add(sb.toString());
break;
}
}
}
return result;
}
class Trie:
def __init__(self):
self.root = {'words_count': 0}
def add(self, word):
cur = self.root
for letter in word:
if letter not in cur:
cur[letter] = {'words_count': 1}
else:
cur[letter]['words_count'] += 1
cur = cur[letter]
cur['END'] = True
self.root['words_count'] += 1
def find(self, word):
cur = self.root
for letter in word:
if letter not in cur:
return 0
cur = cur[letter]
return cur['words_count']
class Trie:
def __init__(self):
self.root = {'words_count': 0}
def add(self, word):
cur = self.root
for letter in word:
if letter not in cur:
cur[letter] = {'words_count': 1}
else:
cur[letter]['words_count'] += 1
cur = cur[letter]
cur['END'] = True
self.root['words_count'] += 1
def find(self, word):
cur = self.root
for letter in word:
if letter not in cur:
return 0
cur = cur[letter]
return cur['words_count']
Build a trie. In every node of the trie have a counter. Whenever you are adding a word, increment counters of all nodes you meet on the way down. Counter represents, how many words have this node in its prefix. Counter == 1 means unique prefix.
Then browse the trie and when you meet a node with counter equal to 1 for the first time on the last way down, you have found a unique prefix for that particular word that goes through this node (note that there is exactly 1 word going through that node).
The code could look something like this:
- Premun October 25, 2014