P114 石头中的珠宝数量

描述#

这个题目说的是，给你一个字符串 J，里面包含不同的大小写字母，表示不同的珠宝。再给你一个字符串 S 表示一堆石头，你要计算出 S 中包含的珠宝数量。

比如说，给你的字符串 J 是：
J = "aBc"
这三个不同的字符表示三种不同的珠宝。给你的字符串 S 是：
S = "aabbB"
字符串 S 中的珠宝有两个 a 和一个 B 共 3 个，因此你要返回数字 3。

代码#

public class AlgoCasts {

  // Time: O(m*n), Space: O(1)
  public int numJewelsInStones(String J, String S) {
    if (J == null || S == null || J.length() == 0 || S.length() == 0)
      return 0;
    int cnt = 0;
    for (int i = 0; i < J.length(); ++i)
      for (int j = 0; j < S.length(); ++j)
        if (J.charAt(i) == S.charAt(j))
          ++cnt;
    return cnt;
  }

  // Time: O(m+n), Space: O(k)
  public int numJewelsInStonesHashMap(String J, String S) {
    if (J == null || S == null || J.length() == 0 || S.length() == 0)
      return 0;
    boolean[] d = new boolean[256];
    int cnt = 0;
    for (int i = 0; i < J.length(); ++i)
      d[J.charAt(i)] = true;
    for (int i = 0; i < S.length(); ++i)
      if (d[S.charAt(i)]) ++cnt;
    return cnt;
  }

}