[LeetCode] 771. Jewels and Stones

发表于 Disqus：

LeetCode 771. Jewels and Stones (宝石与石头) Diffculty: Eazy

Question

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".

Note:

  • S and J will consist of letters and have length at most 50.
  • The characters in J are distinct.

给定字符串 J 代表石头中宝石的类型，和字符串 S 代表你拥有的石头。S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复，J 和 S 中的所有字符都是字母。字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

注意：

  • S 和 J 最多含有 50 个字母。
  • J 中的字符不重复。

Example

Example 1:

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

Example 2:

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

Example 3:

1
2
Input: J = "AB", S = "aAAbbbbBBB"
Output: 5

Solution

题意分析

  • Input：字符串 J 代表石头中宝石的类型（J 中每个字符代表一种宝石类型）；字符串 S 代表拥有的石头（S 中每个字符代表一种石头类型）
  • Output：石头（S）中宝石的数量
  • 即是需要从字符串 S 的所有字符中找到所有包含在字符串 J 中的字符

Java

My Solution 1: Nested double loop

解题思路

首先将字符串（String）转为字符数组（char[]），然后依次遍历两个字符数组，如遍历的 J 字符数组中的元素和 S 字符数组中的元素相同，则计数 +1

解题步骤
  1. 字符串 J 转字符数组 -> jCharArray
  2. 字符串 S 转字符数组 -> sCharArray
  3. 定义结果变量 -> count
  4. 循环 1，遍历字符数组 sCharArray
  5. 循环 2，嵌套在循环 1 中，遍历字符数组 jCharArray
  6. 循环 2 中，判断 sCharArray[i] == jCharArray[j]，如为 true，则 count++
  7. 循环 1 结束后，返回结果变量
Code
初版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int numJewelsInStones(String J, String S) {
    char[] jCharArray = J.toCharArray();
    char[] sCharArray = S.toCharArray();

    int count = 0;
    for (int i = 0; i < sCharArray.length; i++) {
        char sChar = sCharArray[i];
        for (int j = 0; j < jCharArray.length; j++) {
            char jChar = jCharArray[j];
            if (sChar == jChar) {
                count++;
            }
        }
    }
    return count;
 }
优化版
1
2
3
4
5
6
7
8
9
10
11
public int numJewelsInStones(String J, String S) {
    int count = 0;
    for (char j : J.toCharArray()) {
        for (char s : S.toCharArray()) {
            if (j == s) {
                count++;
            }
        }
    }
    return count;
}
Complexity Analysis
  • 时间复杂度：$O(mn)$
  • 空间复杂度：

My Solution 2: Hash Set (Double Loop)

解题思路

首先将字符串（String）转为字符数组（char[]），然后将宝石的类型（J）存到存到哈希集合中，最后循环拥有的宝石（S），判断在哈希集合中是否存在相同的元素。

解题步骤
  1. 字符串 J 转字符数组 -> jCharArray
  2. 定义哈希集合，遍历 jCharArray，将字符串存进哈希集合 -> set
  3. 字符串 S 转字符数组 -> sCharArray
  4. 定义结果变量 -> count
  5. 遍历字符数组 sCharArray
  6. 循环中，判断 set.contains(sCharArray[i])，如为 true，则 count++
  7. 循环结束后，返回结果变量
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int numJewelsInStones(String J, String S) {
    Set<Character> set = new HashSet<>();
    for (char j : J.toCharArray()) {
        set.add(j);
    }

    int count = 0;
    for (char s : S.toCharArray()) {
        if (set.contains(s)) {
            count++;
        }
    }
    return count;
}
Complexity Analysis
  • 时间复杂度：$O(m+n)$
  • 空间复杂度：

LeetCode Discuss Solution 1: Regex (1 line)

Code
1
2
3
public int numJewelsInStones(String J, String S) {
    return S.replaceAll("[^" + J + "]", "").length();
}
Complexity Analysis
  • 时间复杂度：
  • 空间复杂度：
解题思路

利用 Java API 的正则表达式，从拥有的宝石 (字符串 S) 中通过正则表达式找出所有非宝石的石头 (不在字符串 J 中)，然后将非宝石的石头的字符都替换成空字符串，最后输出替换后的长度。

解题步骤
  1. 从字符串 S 中，通过正则表达式 [^J]，匹配所有非宝石的石头 -> tempS
  2. 然后把 tempS 中匹配的结果都替换成空字符串 "" -> tempS
  3. 最后输出 tempS 的长度

LeetCode Discuss Solution 2: indexOf

Code
1
2
3
4
5
6
7
8
9
10
public int numJewelsInStones(String J, String S) {
    int count = 0;

    for (char s : S.toCharArray()) {
        if (J.indexOf(s) > -1) {
            count++;
        }
    }
    return count;
}
Complexity Analysis
  • 时间复杂度：$O(mn)$
  • 空间复杂度：
解题思路

利用 Java API 中 String 的 indexOf() 方法，遍历拥有的宝石 (字符串 S) ，然后将字符传入 indexOf() 方法中，判断在字符串 J 中，是否有对应的宝石类型。

解题步骤
  1. 定义结果变量 -> count
  2. 字符串 S 转字符数组 -> sCharArray
  3. 遍历字符数组 sCharArray
  4. 判断 J.indexOf(s) > -1，如为 true，则 count++
  5. 循环结束后，返回结果变量

注：
String 中的相关 indexOf() 方法：

  • int indexOf(int ch): 返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
  • int indexOf(int ch, int fromIndex): 返回从 fromIndex 位置开始查找指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
  • int indexOf(String str): 返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
  • int indexOf(String str, int fromIndex): 返回从 fromIndex 位置开始查找指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。

Summary

一个问题的各种算法实现，也会因为编程语言的不同而呈现出不同表现方式，除了通用的思路外，也要充分了解各语言提供的 API 和特性。充分利用才能写出时间、空间复杂度都适合具体情况，且简洁易懂易维护的代码。

题中 Note 有写最多含有 50 个字母，实际上没加判断，也通过了 Testcase。
当然，实际开发中，一定要充分考虑各种边界条件和极端情况

References