Share my Java O(nlogn) two pointers solution


  • 0
    Z

    This problem can be easily tackled by two pointers.

    • First off, we convert the two strings into sorted char arrays. This will take O(nlogn) time. (n stands for the longer string's length)
    • Then we will use two pointers ri(for ransonNote) and mi (for magazine) scan through two char arrays. This will cost O(n) complexity.
    • There are only three possibilities in the course of scanning.
      1. Both characters are the same, then ri and mi both advance
      1. caRansom[ri] > caMagazine[mi], for example, 'c' > 'a', we will advance mionly. It is still possible to encounter 'c' in caMagazine
      1. caRansom[ri] < caMagazine[mi], for example, 'a' < 'c', since our char arrays are sorted, it implies 'a' will not exist in caMagazine[mi, caMagazine.length). Hence, we can conclude with a false return.
    • In total, the time complexity is O(nlogn)
    public class Solution {
        public boolean canConstruct(String ransomNote, String magazine) {
            if(ransomNote == null || magazine == null || magazine.length() < ransomNote.length())
                return false;
            char[] caRansom = ransomNote.toCharArray();
            char[] caMagazine = magazine.toCharArray();
            Arrays.sort(caRansom);
            Arrays.sort(caMagazine);
            
            int ri = 0, mi = 0;
            
            while(ri < caRansom.length && mi < caMagazine.length){
                if(caRansom[ri] == caMagazine[mi]){
                    ri++;
                    mi++;
                } else if (caRansom[ri] > caMagazine[mi]){
                    mi++;
                } else {
                    return false;
                }
            }
            
            return ri == caRansom.length ? true : false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.