Space optimized solution


#1

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