Соответствие самого длинного префикса - решение на основе Trie в Java

Опубликовано: 15 Февраля, 2022

Учитывая словарь слов и входную строку, найдите самый длинный префикс строки, который также является словом в словаре.

Примеры:

 Пусть в словаре есть следующие слова:
{are, area, base, cat, care, children, basement}

Ниже приведены некоторые примеры ввода / вывода:
--------------------------------------
Входная строка Выход
--------------------------------------
поставщик кейтеринга
basemexy база
ребенок <Пусто>

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Solution
We build a Trie of all dictionary words. Once the Trie is built, traverse through it using characters of input string. If prefix matches a dictionary word, store current length and look for a longer match. Finally, return the longest match.
Following is Java implementation of the above solution based.

import java.util.HashMap;
  
// Trie Node, which stores a character and the children in a HashMap
class TrieNode {
    public TrieNode(char ch)  {
        value = ch;
        children = new HashMap<>();
        bIsEnd = false;
    }
    public HashMap<Character,TrieNode> getChildren() {   return children;  }
    public char getValue()                           {   return value;     }
    public void setIsEnd(boolean val)                {   bIsEnd = val;     }
    public boolean isEnd()                           {   return bIsEnd;    }
  
    private char value;
    private HashMap<Character,TrieNode> children;
    private boolean bIsEnd;
}
  
// Implements the actual Trie
class Trie {
    // Constructor
    public Trie()   {     root = new TrieNode((char)0);       }    
  
    // Method to insert a new word to Trie
    public void insert(String word)  {
  
        // Find length of the given word
        int length = word.length();
        TrieNode crawl = root;
  
        // Traverse through all characters of given word
        for( int level = 0; level < length; level++)
        {
            HashMap<Character,TrieNode> child = crawl.getChildren();
            char ch = word.charAt(level);
  
            // If there is already a child for current character of given word
            if( child.containsKey(ch))
                crawl = child.get(ch);
            else   // Else create a child
            {
                TrieNode temp = new TrieNode(ch);
                child.put( ch, temp );
                crawl = temp;
            }
        }
  
        // Set bIsEnd true for last character
        crawl.setIsEnd(true);
    }
  
    // The main method that finds out the longest string "input"
    public String getMatchingPrefix(String input)  {
        String result = ""; // Initialize resultant string
        int length = input.length();  // Find length of the input string       
  
        // Initialize reference to traverse through Trie
        TrieNode crawl = root;   
  
        // Iterate through all characters of input string "str" and traverse
        // down the Trie
        int level, prevMatch = 0;
        for( level = 0 ; level < length; level++ )
        {
            // Find current character of str
            char ch = input.charAt(level);    
  
            // HashMap of current Trie node to traverse down
            HashMap<Character,TrieNode> child = crawl.getChildren();                        
  
            // See if there is a Trie edge for the current character
            if( child.containsKey(ch) )
            {
               result += ch;          //Update result
               crawl = child.get(ch); //Update crawl to move down in Trie
  
               // If this is end of a word, then update prevMatch
               if( crawl.isEnd() )
                    prevMatch = level + 1;
            }
            else  break;
        }
  
        // If the last processed character did not match end of a word,
        // return the previously matching prefix
        if( !crawl.isEnd() )
                return result.substring(0, prevMatch);        
  
        else return result;
    }
  
    private TrieNode root;
}
  
// Testing class
public class Test {
   public static void main(String[] args) {
        Trie dict = new Trie();
        dict.insert("are");
        dict.insert("area");
        dict.insert("base");
        dict.insert("cat");
        dict.insert("cater");
        dict.insert("basement");
  
        String input = "caterer";
        System.out.print(input + ":   ");
        System.out.println(dict.getMatchingPrefix(input));              
  
        input = "basement";
        System.out.print(input + ":   ");
        System.out.println(dict.getMatchingPrefix(input));                      
  
        input = "are";
        System.out.print(input + ":   ");
        System.out.println(dict.getMatchingPrefix(input));              
  
        input = "arex";
        System.out.print(input + ":   ");
        System.out.println(dict.getMatchingPrefix(input));              
  
        input = "basemexz";
        System.out.print(input + ":   ");
        System.out.println(dict.getMatchingPrefix(input));                      
  
        input = "xyz";
        System.out.print(input + ":   ");
        System.out.println(dict.getMatchingPrefix(input));
    }
}

Выход:

 поставщик: обслужить
подвал: подвал
являются: являются
arex: являются
basemexz: база
xyz:

Сложность времени: Сложность поиска самого длинного префикса составляет O (n), где n - длина входной строки. Обратитесь к этому, чтобы узнать о временной сложности построения Trie.

Эта статья составлена Рави Чандра Энаганти . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Java

Соответствие самого длинного префикса - решение на основе Trie в Java

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

РЕКОМЕНДУЕМЫЕ СТАТЬИ