最长前缀匹配——一个基于特里的 Java 解决方案
原文:https://www . geesforgeks . org/最长前缀匹配-基于 trie 的 java 解决方案/
给定一个单词字典和一个输入字符串，找到字符串中最长的前缀，它也是字典中的一个单词。
示例:
Let the dictionary contains the following words:
{are, area, base, cat, cater, children, basement}
Below are some input/output examples:
--------------------------------------
Input String Output
--------------------------------------
caterer cater
basemexy base
child < Empty >
解决方案 我们构建一个所有词典单词的 Trie。一旦构建了 Trie，使用输入字符串的字符遍历它。如果前缀匹配词典单词，存储当前长度并寻找更长的匹配。最后，返回最长的匹配。 以下是上述基于解决方案的 Java 实现。
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));
}
}
输出:
caterer: cater
basement: basement
are: are
arex: are
basemexz: base
xyz:
时间复杂度:寻找最长前缀的时间复杂度是 O(n)，其中 n 是输入字符串的长度。构建 Trie 的时间复杂度请参考这个。
本文由 Ravi Chandra Enaganti 整理。如果您发现任何不正确的地方，或者您想分享更多关于上面讨论的主题的信息，请写评论
版权属于：月萌API www.moonapi.com，转载请注明出处
