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 ; } } 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); } } 
Top comments (0)