CODEWITHSUNDEEP
javaarraysstringmethods
Shivam Mishra
Shivam Mishra

Reputation: 31

Check Prefix in an Array

I got correct output but beyond Time Limit.

Question : A list Li containing (not necessarily distinct) N words and Q queries. Each query consists of a string x. For each query, find how many strings in the List Li has the string x as its prefix.\

class Solution{
    static List<Integer> prefixCount(int N, int Q, String li[], String query[])
    {
        List<Integer> list = new ArrayList<>();
        int l,c;
        for(int i=0; i<Q; i++){
            c = 0;
             
            for(int j=0; j<N; j++){
                if(li[j].length()>=query[i].length()){
                if(li[j].substring(0,query[i].length()).equals(query[i])){
                    c++;
                }
                }
            }
            list.add(c);
        }
    return list;
    }
}

How can I optimize the above code?

Upvotes: 0

Views: 564

Answers (1)

Ran94
Ran94

Reputation: 139

Create a Trie with the given strings maintaining a count at each node on how many time the node was travesed while creating a trie.

Now for each prefix String you traverse through the array, if you successfully traverse until your Prefix string length in the Trie, answer for that prefix string is count at the node, else answer is 0.

Upvotes: 1

Related Questions