Leetcode-Day Three

攻城狮佳润技术 2022年11月15日

0 收藏 949 点赞 3,447 浏览 1491 个字

1002. Find Common Characters

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:

1 2	Input: ["bella","label","roller"] Output: ["e","l","l"]

Example 2:

1 2	Input: ["cool","lock","cook"] Output: ["c","o"]

Note:

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

Solution:

Approach One : 先计算出A[0]字符每个字符出现的次数，然后到其余字符串去匹配，min_times为该字符在各字符串出现的最小次数， min_times = min(min_times,count(temp,A[k]));最小为0，即存在一个字符串不含有该字符，

最终min_times的取值就是该字符要放入result中的次数，解决字符重复出现的问题。

Time Complexity :O(n^2)
Space Complexity: O(n)

int (char c,string str)大专栏  Leetcode-Day Threean>
{
    int result = 0;
    for(int i = 0;i < str.size();i++)
    {
        if(str[i] == c)
        {
            result++;
        }
    }
    return result;
}
vector<string> commonChars(vector<string>& A) {
    vector<string> result;
    int min_times = 0;
   for(int i = 0; i < A[0].size();i++)  
   {
      char temp = A[0][i];
      bool flag = true;
      min_times = 0;      for(int j = 0; j < i;j++)
      {
          if(temp == A[0][j])   //判断该字符在前面是否出现过
          {
              flag = false;
          }
      }
      if(flag)  //该字符第一次出现
      {
          for(int h = i; h < A[0].size();h++)
          {
              if(A[0][h] == temp)
              {
                  min_times++;
              }
          }          //得到A[0][i]在第一个字符串出现的次数 times
          for(int k = 1; k < A.size();k++)
          {
              min_times = min(min_times,count(temp,A[k]));
          }
          if(min_times != 0)
          {
              string str;
              stringstream stream;
              stream << temp;
              str = stream.str();
              for(int k = 0;k < min_times;k++)
              {
                  result.push_back(str);
              }
          }
      }
   }
    return result;
}