Facebook Interview Question iOS Developers
Country: United States
Interview Type: Written Test
I'm probably missing the point of this test, as I'm guessing from the suggestion they want you to muck about with implementing a suffix trie, which isn't a natively supported structure in iOS as far as I can tell. But the output can be produced very easily by using a predicate (without any for loops).
Specify a dictionary as an input, it's unclear if the strings are the keys or the values. I've assumed they're the values. I've included a separate method for getting all the values out of the dictionary.
- (NSArray*)arrayOfWordsIn:(NSDictionary*)words thatMatchDotFormat:(NSString*)format
{
NSArray *arrayOfWords = [self arrayFromDictionary:words];
NSString *wildCardString = [format stringByReplacingOccurrencesOfString:@"." withString:@"*"];
NSPredicate *pred = [NSPredicate predicateWithFormat:@"self LIKE %@", wildCardString];
NSArray *arrayMatching = [arrayOfWords filteredArrayUsingPredicate:pred];
return arrayMatching;
}
- (NSArray*)arrayFromDictionary:(NSDictionary*)dictionary
{
NSMutableArray *arrayOfContents = [NSMutableArray new];
for (id key in [dictionary allKeys])
{
[arrayOfContents addObject:dictionary[key]];
}
return [NSArray arrayWithArray:arrayOfContents];
}
1. Store the dictionary in a trie
2. Characters in the pattern string, will be the nodes in trie.
3. Start traversing the trie, top to down,in order of characters in pattern string.
4. Maintain a list of words, and at each step, append the words with extra character in the pattern.
5. Incase there is a '.', append all valid child nodes.
6. Print the word if there is a delimiter saying end of word(usually a flag).
I used a custom data structure, which is a trie. I haven't used a dictionary to do the algorithm but an array instead. if we have a dictionary like the question says, we only need to get the keys from the dictionary and treat them as the words we will search for. skipping this step, this is my objective c example.
the initialise word generator method i believe its not necessary for the interview, since we only need to code the algorithm which is, in fact a DFS algorithm.
#import "WordsGenerator.h"
#import "CRTrieStructure.h"
typedef void(^searchBlock)(NSString *word);
@implementation WordsGenerator
- (CRTrieStructure*)hasObject:(NSString *)object inArray:(NSArray *)container {
__block BOOL hasObject = NO;
__block CRTrieStructure *trie;
[container enumerateObjectsUsingBlock:^(CRTrieStructure *obj, NSUInteger idx, BOOL *stop) {
if ([obj.value isEqualToString:object]) {
hasObject = YES;
*stop = YES;
trie = obj;
}
}];
return (hasObject != NO) ? trie : nil;
}
NSMutableSet *visitedDeepNodes;
-(void)deepFirstSearch:(CRTrieStructure *)searchNode
withPattern:(NSArray *)pattern
forWords:(NSString *)words
completitionBlock:(searchBlock)block {
if (!visitedDeepNodes) {
// first time visiting the recursive function. lazy load the container
// and add the first node to it
visitedDeepNodes = [NSMutableSet set];
[visitedDeepNodes addObject:searchNode];
}
for (CRTrieStructure *newNode in searchNode.childs) {
if (![visitedDeepNodes containsObject:newNode]) {
[visitedDeepNodes addObject:newNode];
if ([newNode.value isEqualToString:[pattern firstObject]] ||
[[pattern firstObject] isEqualToString:@"."]) {
NSMutableArray *newPattern = [pattern mutableCopy];
[newPattern removeObjectAtIndex:0];
// [words enumerateObjectsUsingBlock:^(NSString *word, BOOL *stop) {
NSString *newWord = [words stringByAppendingString:newNode.value];
// }];
if ([newNode.childs count] > 0 ) {
// deepFirstSearch(newNode,newPattern,newWords);
[self deepFirstSearch:newNode
withPattern:newPattern
forWords:newWord
completitionBlock:block];
} else {
block(newWord);
// return block... with the value we need.
}
}
}
}
}
- (void)searchChilds:(NSArray *)container fromPattern:(NSString *)pattern {
NSMutableArray *characters = [NSMutableArray array];
[pattern enumerateSubstringsInRange:NSMakeRange(0, pattern.length)
options:NSStringEnumerationByComposedCharacterSequences
usingBlock:^(NSString *substring,
NSRange substringRange,
NSRange enclosingRange,
BOOL *stop) {
[characters addObject:substring];
}];
// now iterate over the container array to DFS the subchilds. do not add them in case index
// pattern is not equal to specific child
CRTrieStructure *object = [self hasObject:characters[0] inArray:container];
NSString *startPattern = characters[0];
[characters removeObjectAtIndex:0];
NSMutableSet *words = [NSMutableSet set];
[self deepFirstSearch:object
withPattern:characters
forWords:startPattern
completitionBlock:^(NSString *word) {
[words addObject:word];
}];
NSLog(@"words are %@", words);
}
- (void)initializeWordGenerator {
// insert code here...
NSArray *words = @[@"cat", @"cut", @"cot", @"cit", @"bat", @"bet"];
NSMutableArray *containerArray = [NSMutableArray array]; // main container
[words enumerateObjectsUsingBlock:^(NSString *word, NSUInteger idx, BOOL *stop) {
__block CRTrieStructure *object;
__block NSMutableArray *trieContainer = containerArray; // check for level
[word enumerateSubstringsInRange:NSMakeRange(0, word.length)
options:NSStringEnumerationByComposedCharacterSequences
usingBlock:^(NSString *substring,
NSRange substringRange,
NSRange enclosingRange,
BOOL *stop) {
if ([trieContainer count] > 0 ) {
object = [self hasObject:substring inArray:trieContainer];
if (object) {
// we have the object, set the trie container child to be
// current trie and continue in case we have more words.
trieContainer = object.childs;
} else {
CRTrieStructure *trie = [[CRTrieStructure alloc]
initWithValue:substring];
[trieContainer addObject:trie]; // add current substring to container.
trieContainer = trie.childs;
}
} else {
// initialize array.
CRTrieStructure *trie = [[CRTrieStructure alloc]
initWithValue:substring];
[trieContainer addObject:trie]; // add current substring to container.
trieContainer = trie.childs;
}
}];
}];
[self searchChilds:containerArray fromPattern:@"b.t"];
}
@end
and the CRTrieStructure part is
@interface CRTrieStructure : NSObject
@property (nonatomic, copy) NSString *value;
@property (nonatomic) NSMutableArray *childs;
- (instancetype)initWithValue:(NSString *)value;
@end
@implementation CRTrieStructure
- (instancetype)initWithValue:(NSString *)value {
self = [super init];
if (self) {
_value = value;
_childs = [NSMutableArray array];
}
return self;
}
@end
Assuming there is only one "." this is a candidate with linear time.
List<string> GetAllWords(string pattern)
{
if(pattern == null || pattern.IndexOf('.') != pattern.LastIndexOf('.')
{
throw new ArgumentException("The input has an invalid value.....");
}
HashSet<string> dictionary =
GetDictionaryOfValidWords(StringComparison.OrgdinalIgnoreCase);
HashSet<char> a2z = GetA2ZSet();
List<string> results = new List<string>();
// Generate 29 posible candidates
foreach(char c in a2z)
{
string candidate = dictionary.ContainsKey(pattern.Replace('.', c);
if(dictionary.ContainsKey(candidate)
{
results.Add(candidate);
}
}
why not something like this?
+ (BOOL)hasWordsWithPattern:(NSString *)pattern inWords:(NSArray *)words{
NSRegularExpression *expression = [NSRegularExpression regularExpressionWithPattern:pattern
options:NSRegularExpressionCaseInsensitive
error:nil];
for (NSString *s in words) {
if ([expression firstMatchInString:s
options:0
range:NSMakeRange(0, s.length)]) {
NSLog(@"there is a match!");
return YES;
}
}
NSLog(@"sorry, no match found!");
return NO;
}
int main(int argc, const char * argv[])
{
@autoreleasepool
{
NSDictionary *baseDictionary = @{@"1":@"cat",
@"2":@"cut",
@"3":@"cot",
@"4":@"cit",
@"5":@"bat",
@"6":@"bet"};
NSString *pattern = @"c?t";
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF LIKE[c] %@", pattern];
NSArray *resultArray = [[baseDictionary allValues] filteredArrayUsingPredicate:predicate];
NSLog(@"%@", resultArray);
}
return 0;
}
#import <Foundation/Foundation.h>
@interface FBTask : NSObject
- (NSArray *)matchArrayWithPredicateByWordDictionary:(NSDictionary *)wordDictionary withMatchPattern:(NSString *)pattern;
- (NSArray *)matchArrayWithRegexByWordDictionary:(NSDictionary *)wordDictionary withMatchPattern:(NSString *)pattern;
@end
@implementation FBTask
- (NSArray *)matchArrayWithPredicateByWordDictionary:(NSDictionary *)wordDictionary withMatchPattern:(NSString *)pattern
{
NSString *changedPattern = [pattern stringByReplacingOccurrencesOfString:@"." withString:@"?"];
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF LIKE[c] %@", changedPattern];
return [[wordDictionary allValues] filteredArrayUsingPredicate:predicate];
}
- (NSArray *)matchArrayWithRegexByWordDictionary:(NSDictionary *)wordDictionary withMatchPattern:(NSString *)pattern
{
NSMutableArray *bufferArray = [[NSMutableArray alloc] init];
NSRegularExpression *expression = [NSRegularExpression regularExpressionWithPattern:pattern options:NSRegularExpressionCaseInsensitive error:nil];
for (NSString *word in [wordDictionary allValues])
{
if ([[expression matchesInString:word options:0 range:NSMakeRange(0, word.length)] count])
{
[bufferArray addObject:word];
}
}
return [NSArray arrayWithArray:bufferArray];
}
@end
int main(int argc, const char * argv[])
{
@autoreleasepool
{
NSDictionary *wordDictionary = @{@"1":@"cat",
@"2":@"cut",
@"3":@"cot",
@"4":@"cit",
@"5":@"bat",
@"6":@"bet"};
NSString *pattern = @"c.t";
FBTask *task = [[FBTask alloc] init];
NSLog(@"%@", [task matchArrayWithPredicateByWordDictionary:wordDictionary withMatchPattern:pattern]);
NSLog(@"%@", [task matchArrayWithRegexByWordDictionary:wordDictionary withMatchPattern:pattern]);
}
return 0;
}
def isWordPatternInDictionary(pattern, dictionary, suffix = ""):
if len(pattern) == 0:
return suffix in dictionary
if pattern[0] == '*':
for i in range(97,123):
newSuffix = suffix + chr(i)
if isWordPatternInDictionary(pattern[1:], dictionary,newSuffix):
return True
return False
newSuffix = suffix + pattern[0]
return isWordPatternInDictionary(pattern[1:], dictionary, newSuffix)
words = {
"cutter":""
}
print isWordPatternInDictionary("c*tt*r",words)
-(NSArray*)matchTree:(NSArray*)words pattern:(NSString*)pattern
{
NSMutableDictionary* tree = [NSMutableDictionary new];
for(NSString* word in words)
{
NSMutableDictionary* parent = tree;
for(int i = 0; i < [word length]; i++)
{
NSString* token = [word substringWithRange:NSMakeRange(i, 1)];
if(!parent[token])
parent[token] = [NSMutableDictionary new];
parent = parent[token];
}
parent[@""] = [NSMutableDictionary new]; // mark the end of the word
}
return [self findPattern:tree soFar:@"" pattern:pattern];
}
-(NSArray*)findPattern:(NSDictionary*)tree soFar:(NSString*)soFar pattern:(NSString*)pattern
{
if([soFar length] == [pattern length])
{
if(tree[@""])
return @[soFar];
else
return @[];
}
NSString* token = [pattern substringWithRange:NSMakeRange([soFar length], 1)];
if(tree[token])
return [self findPattern:tree[token] soFar:[soFar stringByAppendingString:token] pattern:pattern];
else if([token isEqualToString:@"."])
{
NSMutableArray* combined = [NSMutableArray new];
for (NSString* key in [tree allKeys])
[combined addObjectsFromArray:
[self findPattern:tree[key] soFar:[soFar stringByAppendingString:key] pattern:pattern]];
return combined;
}
else
return @[];
}
I used Trie and a recursive approach.
public List<String> wordsPatternMatching(String str) {
List<String> list = new ArrayList<>();
patternMatch(str.toCharArray(), this, 0, list, "");
return list;
}
private void patternMatch(char[] arr, TrieNode curr, int from, List<String> words, String wordFormed) {
if(from == arr.length) {
if(curr.isEndOfWord) {
words.add(new String(wordFormed));
}
return;
}
if(from >= arr.length)
return;
if(curr.map.containsKey(arr[from])) {
patternMatch(arr, curr.map.get(arr[from]), from+1, words, wordFormed+arr[from]);
} else if(arr[from] == '*') {
Iterator<Character> iterator = curr.map.keySet().iterator();
while(iterator.hasNext()) {
char c = iterator.next();
patternMatch(arr, curr.map.get(c), from+1, words, wordFormed+c);
}
}
}
Here is the C++ solution with running time of O (A^M), where A is # of alphabet letters and M is length of pattern.
void permutate(set<string>&candidate, int pos, string& past ,string& pattern)
{
if (pos == pattern.length())
{
candidate.insert(past);
return;
}
char next = pattern[pos];
if (next != '.')
{
past.push_back(next);
permutate(candidate, pos+1, past, pattern);
} else {
for (int i = 'a'; i <='z'; i++)
{
past.push_back(i);
permutate(candidate, pos+1, past, pattern);
past.pop_back();
}
for (int i = 'A'; i <='Z'; i++)
{
past.push_back(i);
permutate(candidate, pos+1, past, pattern);
past.pop_back();
}
}
}
list<string> find_words(string* words, int len, string pattern)
{
list<string> result;
set<string> prefix;
string past;
permutate(prefix, 0, past, pattern); //(O(A^M)
for (int i = 0; i < len; i++)
{
if (prefix.find(words[i]) != prefix.end())
{
result.push_back(words[i]);//(O( Log (A^M))
}
}
return result;
}
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
public class Trie {
Node rootNode = new Node();
class Node {
private boolean marker;
private Map<Character, Node> map = new HashMap<Character, Node>();
Node addChildCharcter(char ch){
if(!map.containsKey(ch)){
Node temp = new Node();
map.put(ch, temp);
return temp;
} else {
return map.get(ch);
}
}
Node getChildNode(char ch){
return map.get(ch);
}
void setMarker(boolean m){
marker = m;
}
boolean getMarker(){
return marker;
}
public Collection<Character> getAllChildren() {
return map.keySet();
}
}
void insertString(String str){
Node node = rootNode;
int i=0, len = str.length();
for(i=0; i<len; i++){
node = node.addChildCharcter(str.charAt(i));
}
node.setMarker(true);
}
void printAllStrings(){
print(rootNode, "");
}
boolean search(Node node, String str, int index) {
if(index == str.length() && node.marker){
return true;
}
for(Character child : node.getAllChildren()){
if(str.charAt(index) == '.' || str.charAt(index) == child){
Node childNode = node.getChildNode(child);
boolean bRet = search(childNode, str, index+1);
if(bRet){
return true;
}
}
}
return false;
}
void print(Node node, String str) {
if(node.getMarker()){
System.out.println(str);
}
for(Character child : node.getAllChildren()){
Node childNode = node.getChildNode(child);
print(childNode, str + child);
}
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insertString("cut");
trie.insertString("cat");
trie.insertString("cup");
trie.insertString("cot");
// trie.printAllStrings();
System.out.println(trie.search("cup"));
System.out.println(trie.search("cip"));
}
boolean search(String str) {
return search(rootNode, str, 0);
}
}
I used a combination of a couple of the top answers to come up with this solution.
-(NSArray*)findWordWithWildCard:(TrieNode*)node word:(NSString*)searchWord {
NSMutableArray *finalArray = [NSMutableArray new];
searchWord = [searchWord stringByReplacingOccurrencesOfString:@"." withString:@"*"];
if (searchWord.length <= 0) {
return nil;
}
while (searchWord.length != node.level) {
NSString *searchKey = [searchWord substringToIndex:node.level + 1];
for (TrieNode* childToUse in node.children) {
NSString *result = [self node:childToUse containsSimilarString:searchKey];
if (result != nil) {
node = childToUse;
NSString *matchingWord = [self node:node containsSimilarString:searchWord];
if (matchingWord != nil) {
[finalArray addObject:matchingWord];
}
NSArray *resultsArray = [self findWordWithWildCard:node word:searchWord];
if (resultsArray != nil) {
[finalArray addObjectsFromArray:resultsArray];
}
}
}
}
return finalArray;
}
-(NSString*)node:(TrieNode*)node containsSimilarString:searchString {
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"self like %@", searchString];
NSArray *resultArray = [@[node.key] filteredArrayUsingPredicate:predicate];
if (resultArray.count > 0) {
return resultArray.firstObject;
}
return nil;
}
class Node {
var value: Character? = nil
var nodes = Dictionary<Character, Node>()
var word: String? = nil
init() {
}
init(_ value: Character) {
self.value = value
}
}
class Trie {
private (set) var root = Node()
func addWord(_ word: String) {
var node: Node? = root
for c in word.characters {
var n = node!.nodes[c]
if n == nil {
n = Node(c)
node!.nodes[c] = n
}
node = n
}
node!.word = word
}
func findAll(_ match: String) -> [String] {
var res = [String]()
findAll(Array(match.characters), 0, root, &res)
return res
}
private func findAll(_ match: [Character], _ idx: Int, _ node: Node, _ res: inout [String]) {
if idx > match.count - 1 { return }
for node in node.nodes {
let n = node.value
let c = match[idx]
if c == n.value || c == "." {
findAll(match, idx+1, n, &res)
if n.word != nil {
if n.word!.characters.count == match.count {
res.append(n.word!)
}
}
}
}
}
}
let dictionary = Trie()
dictionary.addWord("car")
dictionary.addWord("cat")
dictionary.addWord("cut")
dictionary.addWord("caterpillar")
dictionary.addWord("put")
dictionary.addWord("let")
dictionary.addWord("var")
print(dictionary.findAll("c.r"))
dictionary.addWord("cur")
print(dictionary.findAll("c.."))
class Node {
var value: Character? = nil
var nodes = Dictionary<Character, Node>()
var word: String? = nil
init() {
}
init(_ value: Character) {
self.value = value
}
}
class Trie {
private (set) var root = Node()
func addWord(_ word: String) {
var node: Node? = root
for c in word.characters {
var n = node!.nodes[c]
if n == nil {
n = Node(c)
node!.nodes[c] = n
}
node = n
}
node!.word = word
}
func findAll(_ match: String) -> [String] {
var res = [String]()
findAll(Array(match.characters), 0, root, &res)
return res
}
private func findAll(_ match: [Character], _ idx: Int, _ node: Node, _ res: inout [String]) {
if idx > match.count - 1 { return }
for node in node.nodes {
let n = node.value
let c = match[idx]
if c == n.value || c == "." {
findAll(match, idx+1, n, &res)
if n.word != nil {
if n.word!.characters.count == match.count {
res.append(n.word!)
}
}
}
}
}
}
let dictionary = Trie()
dictionary.addWord("car")
dictionary.addWord("cat")
dictionary.addWord("cut")
dictionary.addWord("caterpillar")
dictionary.addWord("put")
dictionary.addWord("let")
dictionary.addWord("var")
print(dictionary.findAll("c.r"))
dictionary.addWord("cur")
print(dictionary.findAll("c.."))
class Node {
var value: Character? = nil
var nodes = Dictionary<Character, Node>()
var word: String? = nil
init() {
}
init(_ value: Character) {
self.value = value
}
}
class Trie {
private (set) var root = Node()
func addWord(_ word: String) {
var node: Node? = root
for c in word.characters {
var n = node!.nodes[c]
if n == nil {
n = Node(c)
node!.nodes[c] = n
}
node = n
}
node!.word = word
}
func findAll(_ match: String) -> [String] {
var res = [String]()
findAll(Array(match.characters), 0, root, &res)
return res
}
private func findAll(_ match: [Character], _ idx: Int, _ node: Node, _ res: inout [String]) {
if idx > match.count - 1 { return }
for node in node.nodes {
let n = node.value
let c = match[idx]
if c == n.value || c == "." {
findAll(match, idx+1, n, &res)
if n.word != nil {
if n.word!.characters.count == match.count {
res.append(n.word!)
}
}
}
}
}
}
let dictionary = Trie()
dictionary.addWord("car")
dictionary.addWord("cat")
dictionary.addWord("cut")
dictionary.addWord("caterpillar")
dictionary.addWord("put")
dictionary.addWord("let")
dictionary.addWord("var")
print(dictionary.findAll("c.r"))
dictionary.addWord("cur")
print(dictionary.findAll("c.."))
Recursive solution in Swift. Have a good day 😀
class TrieNode {
var value: Character?
var children: [Character: TrieNode] = [:]
weak var parent: TrieNode?
var isWord: Bool = false
init(value: Character?, parent: TrieNode?) {
self.value = value
self.parent = parent
}
func add(child: Character) {
guard children[child] == nil else { return }
children[child] = TrieNode(value: child, parent: self)
}
}
class Trie {
let root: TrieNode
init() {
root = TrieNode(value: nil, parent: nil)
}
func add(word: String) {
guard !word.isEmpty else { return }
let characters = ArraySlice(word)
var currentNode = root
for char in characters {
currentNode.add(child: char)
currentNode = currentNode.children[char]!
}
currentNode.isWord = true
}
func matchingWords(withTerm term: String) -> [String] {
guard !term.isEmpty else { return [] }
let characters = Array(term)
var result: [String] = []
let current = root
helper(term: characters, idx: 0, accumulator: "", node: current, results: &result)
return result
}
func helper(term: [Character], idx: Int, accumulator: String, node: TrieNode, results: inout [String]) {
guard idx < term.count else {
return results.append(accumulator)
}
if term[idx] == "." {
for child in node.children.values {
if let val = child.value {
helper(term: term, idx: idx + 1, accumulator: accumulator + String(val), node: child, results: &results)
}
}
return
}
if let child = node.children[term[idx]] {
let result = child.value == nil ? "" : String(child.value!)
helper(term: term, idx: idx + 1, accumulator: accumulator + result, node: child, results: &results)
}
}
}
Updated
class TrieNode {
var value: Character?
var children: [Character: TrieNode] = [:]
weak var parent: TrieNode?
var isWord: Bool = false
init(value: Character?, parent: TrieNode?) {
self.value = value
self.parent = parent
}
func add(child: Character) {
guard children[child] == nil else { return }
children[child] = TrieNode(value: child, parent: self)
}
}
class Trie {
let root: TrieNode
init() {
root = TrieNode(value: nil, parent: nil)
}
func add(word: String) {
guard !word.isEmpty else { return }
let characters = ArraySlice(word)
var currentNode = root
for char in characters {
currentNode.add(child: char)
currentNode = currentNode.children[char]!
}
currentNode.isWord = true
}
func matchingWords(withTerm term: String) -> [String] {
guard !term.isEmpty else { return [] }
let characters = Array(term)
var result: [String] = []
let current = root
helper(term: characters, idx: 0, accumulator: "", node: current, results: &result)
return result
}
private func helper(term: [Character], idx: Int, accumulator: String, node: TrieNode, results: inout [String]) {
guard idx < term.count else {
if node.isWord {
results.append(accumulator)
}
return
}
if term[idx] == "." {
for child in node.children.values {
if let val = child.value {
helper(term: term, idx: idx + 1, accumulator: accumulator + String(val), node: child, results: &results)
}
}
return
}
if let child = node.children[term[idx]] {
let result = child.value == nil ? "" : String(child.value!)
helper(term: term, idx: idx + 1, accumulator: accumulator + result, node: child, results: &results)
}
}
}
let test = Trie()
test.add(word: "foo")
test.add(word: "koo")
test.add(word: "doo")
test.add(word: "dooo")
debugPrint(test.matchingWords(withTerm: ".o.")) //["koo", "foo", "doo"]
debugPrint(test.matchingWords(withTerm: "....")) // ["dooo"]
debugPrint(test.matchingWords(withTerm: "fo.")) // ["foo"]
debugPrint(test.matchingWords(withTerm: "....")) // ["dooo"]
debugPrint(test.matchingWords(withTerm: "d...")) // ["dooo"]
debugPrint(test.matchingWords(withTerm: "k..")) // ["koo"]
- Youngsam September 09, 2014public class CMain { public static void main(String[] args){ Trie t = new Trie(); t.insert("cat"); t.insert("cot"); t.insert("cut"); t.insert("cit"); t.search2("c.t",t.root); /*t.insert("aseton");*/ } } public class Trie { Node root; public Trie(){ root= new Node(' '); } public void insert(String s){ Node curr=root; if(s.length()==0) curr.marker=true; for(int i=0;i<s.length();i++){ Node n=curr.getNode(s.charAt(i)); if(n!=null) curr=n; else{ curr.children.add(new Node(s.charAt(i))); curr=curr.getNode(s.charAt(i)); } if(i==s.length()-1) curr.marker=true; } } public void search2(String s, Node n){ Node curr=n; while(curr!=null){ for(int i=0;i<s.length();i++){ if(curr.getNode(s.charAt(i))==null && s.charAt(i)!='.') return; else if(curr.getNode(s.charAt(i))!=null && s.charAt(i)!='.'){ curr=curr.getNode(s.charAt(i)); System.out.print(curr.data); } else //if(curr.getNode(s.charAt(i))==null && s.charAt(i)=='.') { System.out.println("\r\n"); for(Node tmp:curr.children){ System.out.print(tmp.data); } System.out.println("\r\n"); for(Node tmp:curr.children){ search2(s.substring(i+1,s.length()),tmp); } } } if(curr.marker==true){ return; } } } } public class Node { char data; boolean marker; Collection<Node> children; public Node(char c){ children=new LinkedList<Node>(); data=c; marker=false; } public Node getNode(char c){ if(children!=null){ for(Node n:children){ if(n.data==c) return n; } } return null; } }