How to Find Common Characters in an array of Strings?

  • 时间：2020-10-12 15:39:01
  • 分类：网络文摘
  • 阅读：112 次

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

Example 1:
Input: [“bella”,”label”,”roller”]
Output: [“e”,”l”,”l”]

Example 2:
Input: [“cool”,”lock”,”cook”]
Output: [“c”,”o”]

1 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] is a lowercase letter

C++ Implementation of Finding Common Characters in an array of Strings

The given problem has constraints on the input and thus we can count the frequencies of each character in each string and store them in a hash map, or simply – a two dimension counter table. The first run is to count the frequency of 26 letters for each string. The second run thus is to find the common letters by iterating over each character and check each string. The minimal number will be used to push to the result vector.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        int count[100][26] = { 0 };
        for (int i = 0; i < A.size(); ++ i) {
            for (const auto &ch: A[i]) {
                // occurence of character in each string
                count[i][ch - 97] ++; 
            }
        }
        vector<string> result;
        for (int i = 0; i < 26; ++ i) {
            int k = INT_MAX;
            for (int j = 0; j < A.size(); j ++) {
                if (count[j][i] == 0) {
                    k = -1; // doesn't appear in every string
                    break;
                }   
                k = min(k, count[j][i]); // the minimal number of the letter
            } 
            while (k -- > 0) {
                result.push_back(std::string(1, (char)(97 + i)));
            }
        }
        return result;
    }
};
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        int count[100][26] = { 0 };
        for (int i = 0; i < A.size(); ++ i) {
            for (const auto &ch: A[i]) {
                // occurence of character in each string
                count[i][ch - 97] ++; 
            }
        }
        vector<string> result;
        for (int i = 0; i < 26; ++ i) {
            int k = INT_MAX;
            for (int j = 0; j < A.size(); j ++) {
                if (count[j][i] == 0) {
                    k = -1; // doesn't appear in every string
                    break;
                }   
                k = min(k, count[j][i]); // the minimal number of the letter
            } 
            while (k -- > 0) {
                result.push_back(std::string(1, (char)(97 + i)));
            }
        }
        return result;
    }
};

Java Implementation of Finding Common Characters in an array of Strings

Java implementation is follows – same idea, but different syntax – and kinda verbose.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public List<String> commonChars(String[] A) {
        int[][] count = new int[100][26];
        for (int i = 0; i < A.length; ++ i) {
            for (int j = 0; j < A[i].length(); ++ j) {
                char ch = A[i].charAt(j);
                // occurence of character in each string
                count[i][ch - 97] ++; 
            }
        }
        List<String> result = new ArrayList<>();
        for (int i = 0; i < 26; ++ i) {
            int k = Integer.MAX_VALUE;
            for (int j = 0; j < A.length; j ++) {
                if (count[j][i] == 0) {
                    k = -1; // doesn't appear in every string
                    break;
                }   
                k = Math.min(k, count[j][i]); // the minimal number of the letter
            } 
            while (k -- > 0) {
                result.add(Character.toString((char)(97 + i)));
            }
        }
        return result;        
    }
}
class Solution {
    public List<String> commonChars(String[] A) {
        int[][] count = new int[100][26];
        for (int i = 0; i < A.length; ++ i) {
            for (int j = 0; j < A[i].length(); ++ j) {
                char ch = A[i].charAt(j);
                // occurence of character in each string
                count[i][ch - 97] ++; 
            }
        }
        List<String> result = new ArrayList<>();
        for (int i = 0; i < 26; ++ i) {
            int k = Integer.MAX_VALUE;
            for (int j = 0; j < A.length; j ++) {
                if (count[j][i] == 0) {
                    k = -1; // doesn't appear in every string
                    break;
                }   
                k = Math.min(k, count[j][i]); // the minimal number of the letter
            } 
            while (k -- > 0) {
                result.add(Character.toString((char)(97 + i)));
            }
        }
        return result;        
    }
}

Both implementation have the time complexity O(NM) where N is the number of strings and M is the average number of characters in a string. The space complexity is O(1).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
洋奶粉频“出事”国产奶粉难“翻身”　 新西兰肉毒杆菌事件中“涉毒”品牌　 食疗养生：治疗牙龈出血的食疗方　 普通大豆粉摇身一变成为神奇保健品　 食品添加剂：合法限量使用就没问题　 武汉市场占八成豆制品来自小作坊　 整治白酒“年份造假”乱象须标准先行　 中医治疗牙周炎的常见饮食疗法　 通过日常饮食疗法如何治疗牙周炎　 炎炎夏日里清凉去火的十种食疗方　
评论列表
添加评论