CareerCup

How about compare two strings using the same iterator i. If any chars[i] is '.' then ignore the equivalence. Else to see chars1[i] == chars2[i].

Why "isMatch("hel.") -> false" ?

I used a trie to store the dictionary.

setup is just ordinary routine of building a trie.

isMatch is similar to the ordinary lookup in trie, with addition to check for wildcard '.' in both words in dict as well as the word in query.

public class wildCardMatchList {
	private class trieNode {
		HashMap<Character, trieNode> children;
		boolean wordEnd;
		public trieNode() {
			children = new HashMap<Character, trieNode>();
			wordEnd = false;
		}
	}
	
	private trieNode root;
	
	public void setup(String[] dict) {
		this.root = new trieNode();
		this.root.wordEnd = true; // for empty string
		for (String word:dict) {
			add(this.root, word);
		}	
	}
	
	public boolean isMatch(String word) {
		return match(this.root, word);
	}
	
	private void add(trieNode parent, String word) {
		if (word.isEmpty()) {
			parent.wordEnd = true;
			return;
		}
		
		char letter = word.charAt(0);
		String surfix = word.substring(1); 
		trieNode child = null;
		
		if (!parent.children.containsKey(letter)) 
			child = new trieNode();
		add(child, surfix);
		parent.children.put(letter, child);
	}
	
	private boolean match(trieNode parent, String word) {
		if (word.isEmpty()) return parent.wordEnd;
		
		char letter = word.charAt(0);
		String surfix = word.substring(1);
		
		if (letter != '.') {
			if (parent.children.containsKey(letter) && match(parent.children.get(letter), surfix)) return true;
			if (parent.children.containsKey('.') && match(parent.children.get('.'), surfix)) return true;
		}
		else { // letter == '.'
			for (trieNode child : parent.children.values()) 
				if (match(child, surfix)) return true;
		}
		return false;
	}
	
	public static void main(String[] args) {
		String[] dict = { "hello", "mi." };
		wildCardMatchList list = new wildCardMatchList();
		list.setup(dict);
		
		String[] words = {"hello", ".ell.", "hel.a", "hel.", "mix"};
		for (String w : words) {
			System.out.println(w + " : " + list.isMatch(w));
		}
	}
}

Test case:

dict = { "hello", "mi." }

Output:

hello : true
.ell. : true
hel.a : false
hel. : false
mix : true
... : true
.... : false
..... : true

import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;


public class StringMatcher {

	HashSet<String> stringSet = new HashSet<String>();
	
	void setup(String[] words){
		if(words != null){
			Collections.addAll(stringSet, words);
		}
	}
	
	 boolean isMatch(String word) {
	
		 if(stringSet.contains(word)){
			 return true;
		 }
		 
		 Iterator<String> stringSetiIterator = stringSet.iterator();
		 
		 while(stringSetiIterator.hasNext()){
			 
			 String current = stringSetiIterator.next();
			 if(current.length() == word.length()){
				 
				 boolean matched = true;
				 for(int i = 0,j =word.length();i< j;i++ ){
					 
					 if(!(current.charAt(i) == word.charAt(i) || current.charAt(i) == '.' || word.charAt(i) == '.')){
						 matched = false;
						 break;
					 }
				 }
				 if(matched){
					 return true;
				 }
			 }
			 
		 }
		 
		 
		 return false;
	}
	 
	 public static void main(String[] args) {
		 String[] dict = { "hello", "mi." };
		 StringMatcher list = new StringMatcher();
			list.setup(dict);
			String[] words = {"hello", ".ell.", "hel.a", "hel.", "mix"};
			for (String w : words) {
				System.out.println(w + " : " + list.isMatch(w));
			}
	}
}