LeetCode/DesignAddAndSearchWordsDataStructure.java at master · Orio77/LeetCode · GitHub

History

65 lines (52 loc) · 1.49 KB

Raw

import java.util.HashMap;

import java.util.Map;

class WordDictionary {

private Node node;

class Node {

private Map<Character, Node> map;

private boolean isEndOfWord;

public Node() {

map = new HashMap<>();

isEndOfWord = false;

}

public WordDictionary() {

this.node = new Node();

}

public void addWord(String word) {

char[] chars = word.toCharArray();

Node curr = this.node;

for (char c : chars) {

curr.map.putIfAbsent(c, new Node());

curr = curr.map.get(c);

}

curr.isEndOfWord = true;

}

public boolean search(String word) {

return search(word, this.node);

}

private boolean search(String word, Node node) {

if (word.length() == 0 && node.isEndOfWord) {

return true;

}

if (word == null || word.length() == 0) {

return false;

}

char[] chars = word.toCharArray();

Node curr = node;

for (char c : chars) {

if (c == '.') {

for (char innerC : curr.map.keySet()) {

if (search(word.substring(word.indexOf(c)+1), curr.map.get(innerC))) {

return true;

}

curr = curr.map.get(c);

if (curr == null) {

return false;

}

return curr.isEndOfWord;

}

LeetCode/DesignAddAndSearchWordsDataStructure.java at master · Orio77/LeetCode · GitHub

Expand file tree

Breadcrumbs

DesignAddAndSearchWordsDataStructure.java

Latest commit

History

Breadcrumbs

DesignAddAndSearchWordsDataStructure.java

File metadata and controls