Algorithm: Leetcode Contest 412

3265. Count Almost Equal Pairs I

Solution

class Solution {
    public int countPairs(int[] nums) {
        // determine whether two integer are almost-equal
        int res = 0;
        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if (isAlmostEqual(nums[i], nums[j])) {
                    // System.out.println((nums[i] + "_" + nums[j]));
                    res++;
                }
            }
        }
                                                
        return res;
    }
    
    
    private boolean isAlmostEqual(int i, int j) {
        // convert to int list
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        
        while(i != 0) {
            list1.add(0, i % 10);
            i /= 10;
        }
        
        while(j != 0) {
            list2.add(0, j % 10);
            j /= 10;
        }
        
        // prefix 0 to make sure two list has the same length
        if (list1.size() != list2.size()) {
            List<Integer> shorter = list1.size() < list2.size() ? list1 : list2;
            List<Integer> longer = shorter.size() == list1.size() ? list2 : list1;
            
            while(shorter.size() != longer.size()){
                shorter.add(0, 0);
            }
        }
        // ensure the sum of each digit is same
        // ensure only 2 position is different 
        int sum1 = 0, sum2 = 0, diff = 0;
        Set<Integer> set = new HashSet<>();
        for(int idx = 0; idx < list1.size(); idx++) {
            set.add(list1.get(idx));
        }
        
        for(int idx = 0; idx < list1.size(); idx++) {
            sum1 += list1.get(idx);
            sum2 += list2.get(idx);
            if (!set.contains(list2.get(idx))) {
                return false;
            }
            if (list1.get(idx) != list2.get(idx)) {
                diff++;
            }
        }
        
        return sum1 == sum2 && diff <= 2;
    }
}