C语言中的字符串操作与数组操作

Question

我在解决一个字符串的换位问题--给定两个字符串s1和s2，写一个函数，如果s2包含s1的换位，则返回true。换句话说，第一个字符串的一个换法是第二个字符串的子串。

例1:输入: s1 = "ab" s2 = "eidbaooo "输出: True

例2：输入：s1="ab" s2="eidboaoo "输出。False

有一个基于数组的解决方案，它存储了子串中每个字母的出现频率，并每次与给定子串进行比较。这个解决方案运行速度比我的快。我不明白为什么，因为我在执行字符串字母的加法时，数组的访问时间是O(1)。这两种解决方案都有相同限制的滑动窗口。那么，到底发生了什么？为什么我的解决方案更慢？

    int findSum(char *string, int substringLength);
    bool checkInclusion(char * s1, char * s2){
        int substringLength = strlen(s1), substringSum = findSum(s1, substringLength);
        int stringLength = strlen(s2);
        if (stringLength < substringLength) return false;
        for (int i = 0; i < stringLength - substringLength + 1; i++, s2++)
        {
           int currentSum = findSum(s2, substringLength);
           if (currentSum == substringSum) return true;
        }
        return false;
    }

    int primes[26] = {2, 599, 23, 809, 11, 47, 3089, 853, 337, 1013, 13, 107, 787, 7, 383, 151, 1493, 
    947, 877, 2141, 431, 211, 59, 911, 23099, 307};
    int findSum(char *string, int substringLength)
    {
       int sum = 0;
       for (int i = 0; i < substringLength; i++)
       {
           sum += primes[*(string + i) - 'a'];
       }
       return sum;
    }

Answer 1

基于数组的解决方案的运行时间为O(n)，因为它对每个字符串循环一次。 然而，你的解决方案的运行时间是O(n*m)，其中n和m是两个字符串的长度。 在 for 循环 checkInclusion，你叫 findSum 它有自己的 for 循环。

其实你并不需要调用 findSum 一遍又一遍。 你可以直接减去每个字符的值。

Answer 2

为了解决这个问题，我们将按照以下步骤进行--。

• 创建两个大小为26的向量cnt1和cnt2。
• 对于i，范围为0至s1
  • 将cnt1[s1[i]-'a']的值增加1。
• j := 0 和 required := s1 的大小
• 对于i，范围为0到s2的大小。
  • x := s2[I]
  • 将cnt2[x-'a']增加1。
  • 如果cnt1[x - 'a']和cnt2[x - 'a'] <= cnt[x - 'a']，那么
    • 需要减少1
  • while j <= i and cnt2[s2[j]- 'a']- 1 >= cnt1[s2[j]- 'a'], do
    • 将cnt2[s2[j]-'a']减少1。
    • 加一
  • 如果i - j + 1 = s1的大小和所需的=0，那么返回true。
• 返回false。

用C++解决。

class Solution {
public:
   bool checkInclusion(string s1, string s2) {
      vector <int> cnt1(26), cnt2(26);
      for(int i = 0; i < s1.size(); i++)cnt1[s1[i] - 'a']++;
      int j = 0;
      int required = s1.size();
      for(int i = 0; i < s2.size(); i++){
         char x = s2[i];
         cnt2[x - 'a']++;
         if(cnt1[x - 'a'] && cnt2[x - 'a'] <= cnt1[x - 'a']) required--;
         while(j <= i && cnt2[s2[j] - 'a'] - 1 >= cnt1[s2[j] - 'a']){
            cnt2[s2[j] - 'a']--;
            j++;
         }
         if(i - j + 1 == s1.size() && required == 0){
            return true;
         }
      }
      return false;
   }
};

Answer 3

解答：

• 把所有的字符都映射到 s1
• 现在把人物地图放在 s2 从指数0到指数 len(s1) — 1
• 如果在这个位置，两张地图相等，你的工作就完成了。
• 否则，每增加一个新角色，就把它添加到 s2 的地图，并删除 i — len(s1) 同图字

一般解决方案模板。

在所有这样的问题中，你从一个较小的字符串中的所有字符的映射开始，并从一个窗口开始。len(s1). 当你遇到一个新的角色，从 s2 你把窗口移动了1，也就是把两个边界推了1。