# old dog, old tricks
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Constraints:
• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.
class Solution {
public String longestCommonPrefix(String[] strs) {
String prefix = "";
if (strs == null || strs.length == 0)
{
return prefix;
}
if (strs.length == 1)
{
return strs[0];
}
prefix = getPrefixByTrie(strs);
return prefix;
}
private static final int MAX_CHARACTERS = 26;
private static class TrieNode
{
TrieNode[] children = new TrieNode[MAX_CHARACTERS];
boolean isLeaf;
public TrieNode()
{
isLeaf = false;
for (int i = 0; i <
MAX_CHARACTERS; i++)
children[i] = null;
}
}
private static TrieNode root;
private static int indexes;
private static void insert(String key)
{
int index;
TrieNode current = root;
for (int level = 0; level < key.length(); level++)
{
index = key.charAt(level) - 'a';
if (current.children[index] == null)
{
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isLeaf = true;
}
private static int countChildren(TrieNode current)
{
int count = 0;
for (int i = 0; i <
MAX_CHARACTERS; i++)
{
if (current.children[i] != null)
{
count++;
indexes = i;
}
}
return count;
}
private static String walkTrie()
{
TrieNode current = root;
indexes = 0;
String prefix = "";
while (countChildren(current) == 1 && current.isLeaf == false)
{
current = current.children[indexes];
prefix += (char)('a' + indexes);
}
return prefix;
}
private static void constructTrie(String[] strs)
{
for (int i = 0; i < strs.length; i++)
{
insert(strs[i]);
}
return;
}
private static String getPrefixByTrie(String[] strs)
{
root = new TrieNode();
constructTrie(strs);
return walkTrie();
}
}
No comments:
Post a Comment