Compare Strings

Tags: Basic Implementation, String, LintCode Copyright, Easy

Question

Problem Statement

Compare two strings A and B, determine whether A contains all of the
characters in B.

The characters in string A and B are all Upper Case letters.

Notice

The characters of B in A are not necessary continuous or ordered.

Example

For A = "ABCD", B = "ACD", return true.

For A = "ABCD", B = "AABC", return false.

题解

题 Two Strings Are Anagrams 的变形题。题目意思是问B中的所有字符是否都在A中，而不是单个字符。比如B=”AABC”包含两个「A」，而A=”ABCD”只包含一个「A」，故返回false. 做题时注意题意，必要时可向面试官确认。

既然不是类似 strstr 那样的匹配，直接使用两重循环就不太合适了。题目中另外给的条件则是A和B都是全大写单词，理解题意后容易想到的方案就是先遍历 A 和 B 统计各字符出现的频次，然后比较频次大小即可。嗯，祭出万能的哈希表。

Python

  1. class Solution:
  2.     """
  3.     @param A : A string includes Upper Case letters
  4.     @param B : A string includes Upper Case letters
  5.     @return :  if string A contains all of the characters in B return True else return False
  6.     """
  7.     def compareStrings(self, A, B):
  8.         letters = collections.defaultdict(int)
  9.         for a in A:
  10.             letters[a] += 1
  12.         for b in B:
  13.             letters[b] -= 1
  14.             if b not in letters or letters[b] < 0:
  15.                 return False
  17.         return True

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: A string includes Upper Case letters
  5.      * @param B: A string includes Upper Case letter
  6.      * @return:  if string A contains all of the characters in B return true 
  7.      *           else return false
  8.      */
  9.     bool compareStrings(string A, string B) {
  10.         if (A.size() < B.size()) return false;
  12.         const int UPPER_NUM = 26;
  13.         int letter_cnt[UPPER_NUM] = {0};
  15.         for (int i = 0; i != A.size(); ++i) {
  16.             ++letter_cnt[A[i] - 'A'];
  17.         }
  18.         for (int i = 0; i != B.size(); ++i) {
  19.             --letter_cnt[B[i] - 'A'];
  20.             if (letter_cnt[B[i] - 'A'] < 0) return false;
  21.         }
  23.         return true;
  24.     }
  25. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param A : A string includes Upper Case letters
  4.      * @param B : A string includes Upper Case letter
  5.      * @return :  if string A contains all of the characters in B return true else return false
  6.      */
  7.     public boolean compareStrings(String A, String B) {
  8.         if (A == null || B == null) return false;
  9.         if (A.length() < B.length()) return false;
  11.         final int UPPER_NUM = 26;
  12.         int[] letter_cnt = new int[UPPER_NUM];
  14.         for (int i = 0; i < A.length(); i++) {
  15.             letter_cnt[A.charAt(i) - 'A']++;
  16.         }
  17.         for (int i = 0; i < B.length(); i++) {
  18.             letter_cnt[B.charAt(i) - 'A']--;
  19.             if (letter_cnt[B.charAt(i) - 'A'] < 0) return false;
  20.         }
  22.         return true;
  23.     }
  24. }

源码分析

Python 的dict就是hash， 所以 Python 在处理需要用到 hash 的地方非常方便。collections 提供的数据结构非常实用，不过复杂度分析起来要麻烦些。

  1. 异常处理，B 的长度大于 A 时必定返回false, 包含了空串的特殊情况。
  2. 使用额外的辅助空间，统计各字符的频次。

复杂度分析

遍历一次 A 字符串，遍历一次 B 字符串，时间复杂度最坏 O(n), 空间复杂度为 O(1).