Leetcode 1268 : Loading...
Please suggest ways for writing this better and cleaner - i am sure there is a better way to iterate through chars of a string… and other improvements. Regards.
class Solution {
private class LLNode
{
public LLNode prev;
public LLNode next;
public String word;
}
private class LL
{
private LLNode head;
private LLNode tail;
private int cnt;
public LL()
{
this.head = new LLNode();
this.tail = new LLNode();
this.head.next = tail;
this.tail.prev = head;
this.cnt = 0;
}
public void Add(String newword)
{
if (this.cnt == 3 &&
newword.compareTo(tail.prev.word) >= 0)
return;
if (this.cnt == 3) Remove();
LLNode curr = this.head.next;
while (curr != this.tail)
{
if (newword.compareTo(curr.word) <= 0) break;
curr = curr.next;
}
// add behind curr
LLNode newNode = new LLNode();
newNode.word = newword;
newNode.prev = curr.prev;
newNode.next = curr;
curr.prev.next = newNode;
curr.prev = newNode;
this.cnt++;
}
public List<String> ToList()
{
List<String> result = new ArrayList<String>();
LLNode curr = this.head.next;
while (curr != this.tail)
{
result.add(curr.word);
curr = curr.next;
}
return result;
}
private void Remove()
{
LLNode condemned = tail.prev;
condemned.prev.next = condemned.next;
condemned.next.prev = condemned.prev;
condemned.prev = condemned.next = null;
this.cnt--;
}
}
private class TrieNode
{
public TrieNode[] kids;
public LL minWords;
public TrieNode()
{
this.kids = new TrieNode[26];
this.minWords = new LL();
}
}
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
TrieNode root = new TrieNode();
// Load products
for (String p : products)
{
List<TrieNode> parents = new ArrayList<TrieNode>();
TrieNode curr = root;
for (String cs : p.split(""))
{
char c = cs.charAt(0);
if (curr.kids[c - 'a'] == null)
curr.kids[c - 'a'] = new TrieNode();
parents.add(curr);
curr = curr.kids[c - 'a'];
}
// curr is a product, update all traversed nodes
// add the node first to include self
parents.add(curr);
for (TrieNode tn : parents) tn.minWords.Add(p);
}
List<List<String>> result = new ArrayList<List<String>>();
int listCount = 0;
TrieNode curr = root;
for (String cs : searchWord.split(""))
{
char c = cs.charAt(0);
if (curr.kids[c - 'a'] == null) break;
curr = curr.kids[c - 'a'];
result.add(curr.minWords.ToList());
listCount++;
}
for (int i=listCount; i<searchWord.length(); i++)
result.add(new ArrayList<String>());
return result;
}
}