771. 宝石与石头

难度: 简单

来源: 每日一题 2023.07.24

---

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

字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

示例 1：

输入：jewels = "aA", stones = "aAAbbbb"
输出：3

示例 2：

输入：jewels = "z", stones = "ZZ"
输出：0

提示：

• 1 <= jewels.length, stones.length <= 50
• jewels 和 stones 仅由英文字母组成
• jewels 中的所有字符都是 唯一的

class Solution {
    public int numJewelsInStones(String jewels, String stones) {

    }
}

分析与题解

---

• 暴力法

  接雨水我唯唯诺诺, 算宝石我重拳出击.

  这个题目比较简单,我们只需要利用 Java 中的API contains 即可一次遍历完成整个题目.

  整个解题过程如下所示.

  class Solution {
      public int numJewelsInStones(String jewels, String stones) {
          int result = 0, length = stones.length();
          for(int i = 0; i < length; i++) {
              if(jewels.contains(stones.subSequence(i, i+1))) {
                  result++;
              }
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 只遍历一次, 时间复杂度与 stones 的长度成线性正相关关系.
  • 空间复杂度: O(1), 只创建了常量级别的空间.

  结果如下所示.