Java O(m+n)


  • 0
    T
    public class Solution {
        //sort ransom note and magazine string in non-decreasing order.
        //Create pointer for each string representing the current position in each string respectively.
        //If ransom[i] == magazine[j] -> i++ j++
        //Else j++.
        //If j == magazine.length && i < ransom.length return false.
        //If j < magazine.length && i == ransom.length return true.
        //Time complexity O(m+n) m -- length of ransomNote n -- length of magazine
        public boolean canConstruct(String ransomNote, String magazine) {
            char[] ransomArr = new char[ransomNote.length() ];
            char[] magaziArr = new char[magazine.length() ];
            for(int i = 0; i < ransomNote.length(); i++){
                ransomArr[i] = ransomNote.charAt(i);
            }
            for(int i = 0; i < magazine.length(); i++){
                magaziArr[i] = magazine.charAt(i);
            }
            Arrays.sort(ransomArr);
            Arrays.sort(magaziArr);
            int m = 0, n = 0;
            while(m < ransomArr.length){
                if(n == magaziArr.length){
                    return false;
                }
                else{
                    if(ransomArr[m] == magaziArr[n]){
                        m++;
                        n++;
                    }
                    else{
                        n++;
                    }
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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