[LeetCode] 208. Implement Trie (Prefix Tree)

轉自LeetCode

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

<Solution>

這題是要實作一個資料結構，叫 Trie (發音同 try)，也可叫 Prefix Tree

可以用來在字串裡面，快速搜尋特定的 key

詳細說明可以看這裡

code 如下

Java

	class Trie {
	private TrieNode mRoot;
	/** Initialize your data structure here. */
	public Trie() {
	mRoot = new TrieNode();
	}
	/** Inserts a word into the trie. */
	public void insert(String word) {
	TrieNode node = mRoot;
	for(final char c : word.toCharArray()) {
	if(!node.containsKey(c)) {
	node.put(c, new TrieNode());
	}
	node = node.get(c);
	}
	node.setEnd();
	}
	/** Returns if the word is in the trie. */
	public boolean search(String word) {
	final TrieNode node = searchPrefix(word);
	return node != null && node.isEnd();
	}
	/** Returns if there is any word in the trie that starts with the given prefix. */
	public boolean startsWith(String prefix) {
	final TrieNode node = searchPrefix(prefix);
	return node != null;
	}
	private TrieNode searchPrefix(final String prefix) {
	TrieNode node = mRoot;
	for(final char c : prefix.toCharArray()) {
	if(node.containsKey(c)) {
	node = node.get(c);
	}
	else {
	return null;
	}
	}
	return node;
	}
	}
	class TrieNode {
	private static final int LEN = 26;
	private TrieNode[] mList;
	private boolean mIsEnd;
	public TrieNode() {
	mList = new TrieNode[LEN];
	mIsEnd = false;
	}
	public void setEnd() {
	mIsEnd = true;
	}
	public boolean isEnd() {
	return mIsEnd;
	}
	public void put(final char key, final TrieNode node) {
	mList[key - 'a'] = node;
	}
	public TrieNode get(final char key) {
	return mList[key - 'a'];
	}
	public boolean containsKey(final char key) {
	return mList[key - 'a'] != null;
	}
	}
	/**
	* Your Trie object will be instantiated and called as such:
	* Trie obj = new Trie();
	* obj.insert(word);
	* boolean param_2 = obj.search(word);
	* boolean param_3 = obj.startsWith(prefix);
	*/

view raw prefixTree.java hosted with ❤ by GitHub

Kotlin

	class Trie() {
	/** Initialize your data structure here. */
	private val root = TrieNode()
	/** Inserts a word into the trie. */
	fun insert(word: String) {
	var node = root
	for(c in word) {
	if(!node.containsKey(c)) {
	node.put(c, TrieNode())
	}
	node = node.get(c)!!
	}
	node.setEnd()
	}
	/** Returns if the word is in the trie. */
	fun search(word: String): Boolean {
	val node = searchPrefix(word)
	return node != null && node!!.checkIsEnd()
	}
	/** Returns if there is any word in the trie that starts with the given prefix. */
	fun startsWith(prefix: String): Boolean {
	return searchPrefix(prefix) != null
	}
	private fun searchPrefix(prefix: String): TrieNode? {
	var node = root
	for(c in prefix) {
	if(node.containsKey(c)) {
	node = node.get(c)!!
	} else {
	return null
	}
	}
	return node
	}
	}
	class TrieNode {
	private val list = arrayOfNulls<TrieNode>(26)
	private var isEnd = false
	fun setEnd() {
	isEnd = true
	}
	fun checkIsEnd(): Boolean {
	return isEnd
	}
	fun put(key: Char, node: TrieNode) {
	list[key - 'a'] = node
	}
	fun get(key: Char): TrieNode? {
	return list[key - 'a']
	}
	fun containsKey(key: Char): Boolean {
	return list[key - 'a'] != null
	}
	}
	/**
	* Your Trie object will be instantiated and called as such:
	* var obj = Trie()
	* obj.insert(word)
	* var param_2 = obj.search(word)
	* var param_3 = obj.startsWith(prefix)
	*/

view raw implement_trie.kt hosted with ❤ by GitHub