Egoralve
BAN USERpublic static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("acb");
words.add("abc");
words.add("abcd");
words.add("abe");
words.add("ab");
words.add("aces");
words.add("ey");
Dictionary di = new Dictionary(words);
System.out.println(di.getMinSizeWordsContained(new char[]{'a','b','c'}));
}
// create class dictionary which contains a TreeMap with key = word.length and value= List<String> wordsWithTheSameSize
// it allows us to decrease scope of search (if we have 3 chars then we start search from words only with size 3 and unless we find them we take words with the following size)
public class Dictionary {
private TreeMap<Integer,List<String>> dictionary = new TreeMap<>();
public Dictionary(List<String> words) {
if (Helper.isEmpty(words)) {
throw new RuntimeException("Dictionary can not be empty");
}
for (String word : words) {
List<String> sameSizeWords = dictionary.get(word.length());
if (!Helper.isEmpty(sameSizeWords)) {
sameSizeWords.add(word);
} else {
sameSizeWords = new ArrayList();
sameSizeWords.add(word);
dictionary.put(word.length(), sameSizeWords);
}
}
}
public List<String> getMinSizeWordsContained(char[] chars) {
if (Helper.isEmpty(chars)) {
return null;
}
conditionValidation(chars);
for (int i = chars.length; i <= dictionary.lastKey(); i++) {
List<String> minWords = getListHits(chars, dictionary.get(i));
if (!Helper.isEmpty(minWords)) {
return minWords;
}
}
return null;
}
private List<String> getListHits(char[] chars, List<String> words) {
if (Helper.isEmpty(chars) || Helper.isEmpty(words)) {
return null;
}
List<String> hits = new ArrayList();
for (String word : words) {
if (isWordContainsChars(word, chars)) {
hits.add(word);
}
}
return hits;
}
private boolean isWordContainsChars(String word, char[] chars) {
for (char letter : chars) {
if(!word.contains(String.valueOf(letter))) {
return false;
}
}
return true;
}
private void conditionValidation(char[] chars) {
if (chars.length > dictionary.lastKey()) {
throw new RuntimeException("Count of chars is higher than the max word length in dictionary");
}
}
}
// just helper class
public class Helper {
public static boolean isEmpty(List<String> words){
if (words == null || words.isEmpty()) {
return true;
}
return false;
}
public static boolean isEmpty(char[] chars){
if (chars == null || chars.length() == 0) {
return true;
}
return false;
}
}
- Egoralve July 19, 2016