Count prefix and suffix I and II

Count prefix and suffix I

Brute force approach:

TC: O(n^2*m), n is words.length and m is the length of the word[i] i>=0 && <n

class Solution {
    public int countPrefixSuffixPairs(String[] words) {
        int count =0;
        for(int i=0;i<words.length;i++){
            for(int j = 0;j<words.length;j++){
                if(i==j || words[i].length() > words[j].length() || i > j) continue;
                if(check(words[i],words[j])){
                    count++;
                }
            }
        }
        return count;
    }
    public boolean check(String a , String b){
        int i=0;
        int j = b.length()-a.length();
        while(i<a.length() && j< b.length()){
            if(a.charAt(i) != b.charAt(i)  || a.charAt(i)!=b.charAt(j)){
                return false;
            }
            i++;j++;
        }
        //System.out.println(j==b.length());
        return true ;
    }
}

Count Prefix and suffix II

Fun Fact: I never could have come up with this intuition if not for the hints given in the question
TC: O(n*m) where n is the length of the words[] and m is length of words[i]
SC: quantifying exact space used by Trie is bit trivial and not so straight forward because of ever growing nature of trie
Using trie ds:

class Solution {
    public long countPrefixSuffixPairs(String[] words) {
        Trie t = new Trie();
        long count =0;
        for(int i=0;i<words.length;i++){
            count+= t.insert(words[i]);
        }
        return count;
    }
}
class Trie{
    Node root;
    public Trie(){
        root = new Node();
    }
    public long insert(String s){
        Node node = root;
        long count =0;
        for(int i =0;i<s.length();i++){
            char I = s.charAt(i);
            char J = s.charAt(s.length()-i-1);
            Pair p = new Pair(I,J);
            if(!node.isPresent(p)){
                node.add(p);
            }
            node = node.get(p);
            if(node.isEnd()) {
                count+=node.eCount();
            }
        }
        node.setEnd();
        node.incC();
        return count;
    }
}
class Node{
    Map<Pair,Node> map =  new HashMap<>();
    boolean end;
    long eCount =0;
    public void add(Pair p){
        map.put(p,new Node());
    }
    public boolean isPresent(Pair p){
        return map.containsKey(p);
    }
    public Node get(Pair p){
        return map.get(p);
    }
    public void setEnd(){this.end = true;}
    public boolean isEnd(){return this.end;}
    public void incC(){
        eCount++;
    }
    public long eCount(){return this.eCount;}
}
class Pair{
    public char i;
    public char j;
    public Pair(char i, char j){
        this.i = i;
        this.j = j;
    }
    @Override
    public boolean equals(Object p){
        if(this == p) return true;
        if(p ==null || this.getClass()!=p.getClass()) return false;
        Pair  pair = (Pair)p;
        return (pair.i == this.i) && (pair.j == this.j);
    }
    @Override
    public int hashCode(){
        return Objects.hash(i,j);
    }
}