Simple Java Solution Using Sorting (what's the complexity of this?)


  • 0
    F
     public boolean canConstruct(String ransomNote, String magazine) {
           if(ransomNote.length()==0){
               return true;
           }
           if(magazine.length()==0){
               return false;
           }
            char magCharArr[] = magazine.toCharArray();
            char ranCharArr[] = ransomNote.toCharArray();
            Arrays.sort(magCharArr);
            Arrays.sort(ranCharArr);
            int i=0;
            for(char c:magCharArr){
                if(ranCharArr[i]==c){
                    i++;
                    if(i==ranCharArr.length){
                        return true;
                    }
                }
            }
            return false;
        }
    

    I am not good at thinking about BigO. I think this solution is O(n) ?
    2 Sorting is 2 * nlogn, 1 for loop is n, so O(n) in total? Please correct me if I am wrong. Thanks!!


  • 0
    K

    No need to sort. Just count and compare. I see one-liner again...

    class Solution(object):
        def canConstruct(self, ransomNote, magazine):
            """
            :type ransomNote: str
            :type magazine: str
            :rtype: bool
            """
            # https://discuss.leetcode.com/topic/53902/o-m-n-one-liner-python
            # Counter1 - Counter2 doesn't allow negative number, for (k, v), if v <= 0, it will be removed
            # return not collections.Counter(ransomNote) - collections.Counter(magazine)
            c_ransomNote, c_magazine = collections.Counter(ransomNote), collections.Counter(magazine)
            return all(c_magazine[k] >= v for k, v in c_ransomNote.iteritems())
    

Log in to reply
 

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