public class Solution {
static class Trie
{
boolean isLeave;
Trie[] children = new Trie[26];
Trie()
{
isLeave=false;
for(int i=0;i<26;i++)
{
children[i] = null;
}
}
}
static Trie root;
public static void insert(String key)
{
int level;
int index;
int len= key.length();
Trie head = root;
for(level=0;level<len;level++)
{
index = key.charAt(level)-‘a’;
if(head.children[index] == null)
{
head.children[index] = new Trie();
}
head = head.children[index];
}
head.isLeave=true;
}
public static boolean search(String key)
{
int level;
int index;
int len= key.length();
Trie head = root;
for(level=0;level<len;level++)
{
index = key.charAt(level)-'a';
if(head.children[index] == null)
{
return false;
}
head = head.children[index];
}
return head.isLeave==true ? true : false;
}
class Data
{
int cnt;
int index;
Data(int cnt, int index)
{
this.cnt=cnt;
this.index= index;
}
}
public ArrayList<Integer> solve(String A, ArrayList<String> B)
{
ArrayList<Integer> res = new ArrayList<>();
if(B==null || B.size()==0)
{
return res;
}
root = new Trie();
String [] praisingWords = A.split("_");
for(String word : praisingWords)
{
Solution.insert(word);
}
ArrayList<Data> list = new ArrayList<>();
int cnt;
for(int i=0;i<B.size();i++)
{
String [] praisingWordInReviews = B.get(i).split("_");
cnt = 0;
for(String praisingWordInReview : praisingWordInReviews)
{
if(Solution.search(praisingWordInReview))
{
cnt++;
}
}
list.add(new Data(cnt, i));
}
Collections.sort(list, new Comparator<Data>(){
@Override
public int compare(Data a, Data b)
{
if(a.cnt == b.cnt)
{
return a.index - b.index;
}
return b.cnt - a.cnt;
}
});
for(Data d :list )
{
res.add(d.index);
}
return res;
}
}
indent preformatted text by 4 spacesPreformatted text