LeetCode Jewels and Stones 珠寶與石頭

雖然常在網路上(PTT SOFT_JOB)常聽到要刷LeetCode，但直到今天才來玩看看，下面是我隨便挑的一個演算法(algorithm)的簡單題目，Jewels and Stones 珠寶與石頭。

題目如下：

You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

給兩個輸入參數字串分別為J和S，J代表珠寶種類，S代表石頭。石頭中的每一個字母(character)代表你擁有的石頭，你想要知道你的石頭中有幾顆是珠寶。

J中的字母是保證唯一的。J及S中皆為字母，大小寫敏感，也就是小寫"a"與大寫"A"是不同的，字數皆小餘50個字。

例如

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

一開始直覺想到的解法就是字串轉陣列，跑雙重迴圈來兩兩比較，如果相同則數數加一。

public static int numJewelsInStones(String J, String S) {
    int count = 0;
    for(int n = 0; n < J.length() ; n++) {
        for(int m = 0; m < S.length(); m++) {
            char j = J.charAt(n);
            char s = S.charAt(m);
            if(j == s) {
                count++;
            }
        }
    }
    
    return count;
}

雖然結果正確，但這樣的做法時間複雜度為O(N²)，效率不好。

在下面的相關主題看到Hash Map，馬上想到用Map來處理，應該會比較快。

public static int numJewelsInStones(String J, String S) {
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    for(int n = 0; n < J.length(); n++) {
        map.put(J.charAt(n), 1);
    }
    int count = 0;
    for(int m = 0; m < S.length(); m++) {
        Integer c = map.get(S.charAt(m));
        if(c != null) {
            count++;
        }
    }
    return count;
}

或String轉char陣列來用foreach處理。

public static int numJewelsInStones3(String J, String S) {
    System.out.println("numJewelsInStones3");
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    for (char j : J.toCharArray()) {
        map.put(j, 1);
    }
    
    int count = 0;
    for (char s : S.toCharArray()) {
        if (map.get(s) != null) {
            count++;
        }
    }
    return count;
}

或是使用HashSet

public static int numJewelsInStones(String J, String S) {
    
    Set<Character> set = new HashSet<Character>();
    for(int n = 0; n < J.length(); n++) {
        set.add(J.charAt(n));
    }
    int count = 0;
    for(int m = 0; m < S.length(); m++) {
        if(set.contains(S.charAt(m))) {
            count++;
        }
    }
    return count;
}

測試

import org.apache.commons.text.RandomStringGenerator;

public static void main(String[] args) {
    String J = "aAbBcCdDeEfFgG"; // 珠寶種類
    
    char[][] pairs = {{'a','z'},{'A','Z'}}; // 隨機字串範圍
    int length = 10000; // 隨機字串長度
    RandomStringGenerator generator = new RandomStringGenerator.Builder().withinRange(pairs).build();
    String S = generator.generate(length); // 產生 "a - z", "A - Z"隨機字串 
    
    long startTime = System.nanoTime();
    
    int jewelNumber = numJewelsInStones(J, S);
    
    long endTime = System.nanoTime();
    
    System.out.println("Jewel Number:" + jewelNumber);
    System.out.println("Execution Time:" + (endTime - startTime) + " nanosecond");
}

從這題目可以學到，在比較兩個陣列的內容時，應該利用Map來處理，而不要使用雙迴圈。

參考：

• Java 隨機產生字串