Algorithm: Leetcode Contest 385

Find the Length of the Longest Common Prefix

You are given two arrays with positive integers arr1 and arr2.

A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, 123 is a prefix of the integer 12345, while 234 is not.

A common prefix of two integers a and b is an integer c, such that c is a prefix of both a and b. For example, 5655359 and 56554 have a common prefix 565 while 1223 and 43456 do not have a common prefix.

You need to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.

Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0.

Solution 1

public int longestCommonPrefix(int[] arr1, int[] arr2) {
    int maxPrefix = 0;
    int tempPrefix = 0;

    for(int a: arr1) {
        for(int b: arr2) {
            tempPrefix = getPrefix(a, b);
            if (tempPrefix > maxPrefix) {
                maxPrefix = tempPrefix;
            }
        }
    }

    return maxPrefix;
}

private int getPrefix(int a, int b) {
    while (a != b) {
        if (a > b) {
            a /= 10;
        } else {
            b /= 10;
        }
    }

    // big == small, count its bits
    int count = 0;
    while (a != 0) {
        count++;
        a /= 10;
    }

    return count;
}

Solution 2

class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        TrieNode head = buildTrie(arr1);
        int maxPrefix = 0, curPrefix = 0;
        
        for(int i: arr2) {
            curPrefix = findPrefix(head, i);
            if (curPrefix > maxPrefix) {
                maxPrefix = curPrefix;
            }
        }
        
        return maxPrefix;
    }
    
    private int findPrefix(TrieNode head, int i) {
        int prefix = 0;
        TrieNode curNode = head;
        String val = String.valueOf(i);
        
        for(char c: val.toCharArray()) {
            if (curNode.next[c - '0'] == null) {
                break;
            } else {
                prefix++;
                curNode = curNode.next[c - '0'];
            }
        }
        
        return prefix;
    }
    
    private TrieNode buildTrie(int[] arr) {
        TrieNode head = new TrieNode(-1);
        TrieNode temp;
        int mod = 0, rev = 0;
        String str = "";
        for(int i: arr) {
            temp = head;
            str = String.valueOf(i);
            for(char c: str.toCharArray()) {
                if (temp.next[c - '0'] == null) {
                    temp.next[c - '0'] = new TrieNode(c - '0');
                }
                temp = temp.next[c - '0'];
            }
        }
        
        return head;
    }
    
    
    private class TrieNode {
        int val;
        
        TrieNode[] next;
        
        public TrieNode(int val) {
            this.val = val;
            next = new TrieNode[10];
        }
    }
}

Retro

• The recognition is not good enough, didn’t figure out this is Trie challenge
• when involve integer, cannot use reverse integer to build the trie, cause 10’s reverse is not 01, it’s 1, so need to convert integer to string to build the trie.
• API: using String.valueOf to convert integer to string

Count Prefix and Suffix Pairs II

this is the follow up of first question of this contest

Solution 1 (causing TLE)

this brute force solution can solve the base question, while cannot solve this one

class Solution {
    public int countPrefixSuffixPairs(String[] words) {
        int count = 0;
        for(int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (isPrefixSuffix(words[i], words[j])) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private boolean isPrefixSuffix(String str1, String str2) {
        return str2.startsWith(str1) && str2.endsWith(str1);
    }
}

Solution 2

In this solution, we build a trie, whose key is the combination of string prefix & suffix

class Solution {
    public int countPrefixSuffixPairs(String[] words) {
        TrieNode head = new TrieNode();
        TrieNode cur = head;
        
        int res = 0;
        
        for (String word: words) {
            cur = head;
            for(int i = 0; i < word.length(); i++) {
                int key = word.charAt(i) * 128 + word.charAt(word.length() - 1 - i);
                if (cur.next.get(key) == null) {
                    cur.next.put(key, new TrieNode());
                }
                
                cur = cur.next.get(key);
                res += cur.ends;
            }
            
            cur.ends++;
        }
        
        return res;
    }
    
    private class TrieNode {
        Map<Integer, TrieNode> next;
        int ends;
        
        public TrieNode() {
            next = new HashMap<>();
            ends = 0;
        }
    }
}

Retro

• When there is prefix issue, always think if Trie could solve it
• the design of key in solution is very elegant
  • the combination of prefix + suffix as key itself is very inspiring
  • how to combine them is also inspiring