LeetCode 383. Ransom Note (JAVA)

https://leetcode.com/problems/ransom-note/description/

Ransom Note - LeetCode

 

문제

문제에서 2개의 문자열(ransomNote, magazine)이 주어진다.
magazine을 구성하는 문자를 이용하여 ransomNote와 동일한 문자열을 만들 수 있는냐가 문제의 핵심이다.
canConstruct("aab", "baa"); -> true

ransomNote and magazine consist of lowercase English letters.

소문자로만 이루어져서 길이 26의 int배열을 만들고 magazine의 개수를 넣어준다.

배열과 ransomNote를 비교하여 T/F 리턴

 

public static boolean canConstruct(String ransomNote, String magazine) {

    // 소문자 배열을 만들어서 magzine 넣는다.
    int[] mag = new int[26];
    for (char m : magazine.toCharArray()) {
        int idx = m - 97;
        mag[idx]++;
    }

    // ransomNote 돌려가면서 배열에 있는지 확인한다.
    for (char r : ransomNote.toCharArray()) {
        int idx = r - 97;
        if (mag[idx] == 0) return false;
        mag[idx]--;
    }

    // for문을 다 돌았으면 true 리턴한다.
    return true;
}

시간복잡도 : O(n)