LeetCode – Agregar y buscar palabras – Diseño de estructura de datos (Java)

Diseñe una estructura de datos que admita las siguientes dos operaciones:

void addWord(word)
bool search(word)

search (word) puede buscar una palabra literal o una cadena de expresión regular que contenga solo letras az o .. A. significa que puede representar cualquier letra.

Solución Java 1

Este problema es similar con Implement Trie. La solución 1 a continuación usa la misma definición de un nodo trie. Para manejar el «.» En caso de este problema, necesitamos buscar todas las rutas posibles, en lugar de una sola.

TrieNode

class TrieNode{
    char c;
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    boolean isLeaf;
 
    public TrieNode() {}
 
    public TrieNode(char c){
        this.c = c;
    }
}

WordDictionary

public class WordDictionary {
    private TrieNode root;
 
    public WordDictionary(){
        root = new TrieNode();
    }
 
    // Adds a word into the data structure.
    public void addWord(String word) {
        HashMap<Character, TrieNode> children = root.children;
 
        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);
 
            TrieNode t = null;
            if(children.containsKey(c)){
                t = children.get(c);
            }else{
                t = new TrieNode(c);
                children.put(c,t);
            }
 
            children = t.children;
 
            if(i == word.length()-1){
                t.isLeaf = true;
            }
        }
    }
 
    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
       return dfsSearch(root.children, word, 0);
 
    }
 
     public boolean dfsSearch(HashMap<Character, TrieNode> children, String word, int start) {
        if(start == word.length()){
            if(children.size()==0) 
                return true; 
            else
                return false;
        }
 
        char c = word.charAt(start);    
 
        if(children.containsKey(c)){
            if(start == word.length()-1 && children.get(c).isLeaf){
                return true;
            }
 
            return dfsSearch(children.get(c).children, word, start+1);
        }else if(c == '.'){
            boolean result = false;
            for(Map.Entry<Character, TrieNode> child: children.entrySet()){
                if(start == word.length()-1 && child.getValue().isLeaf){
                    return true;
                } 
 
                //if any path is true, set result to be true; 
                if(dfsSearch(child.getValue().children, word, start+1)){
                    result = true;
                }
            }
 
            return result;
        }else{
            return false;
        }
    }
}

¿Cómo verificar si una matriz contiene un valor en Java de manera eficiente?

Solución Java 2: uso de Array en lugar de HashMap

class TrieNode{
    TrieNode[] arr;
    boolean isLeaf;
 
    public TrieNode(){
        arr = new TrieNode[26];
    }    
}
 
public class WordDictionary {
    TrieNode root;
 
    public WordDictionary(){
        root = new TrieNode();
    }
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode p= root;
        for(int i=0; i<word.length(); i++){
            char c=word.charAt(i);
            int index = c-'a';
            if(p.arr[index]==null){
                TrieNode temp = new TrieNode();
                p.arr[index]=temp;
                p=temp;
            }else{
                p=p.arr[index];
            }
        }
 
        p.isLeaf=true;
    }
 
    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        return dfsSearch(root, word, 0);     
    }
 
   public boolean dfsSearch(TrieNode p, String word, int start) {
		if (p.isLeaf && start == word.length())
			return true;
 
		if (start >= word.length())
			return false;
 
		char c = word.charAt(start);
 
		if (c == '.') {
			boolean tResult = false;
			for (int j = 0; j < 26; j++) {
				if (p.arr[j] != null) {
					if (dfsSearch(p.arr[j], word, start + 1)) {
						tResult = true;
						break;
					}
				}
			}
 
			if (tResult)
				return true;
		} else {
			int index = c - 'a';
 
			if (p.arr[index] != null) {
				return dfsSearch(p.arr[index], word, start + 1);
			} else {
				return false;
			}
		}
 
		return false;
	}
}

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta