时间戳

首页 > 解决方案 > C中的字符串操作与数组操作

c - C中的字符串操作与数组操作

问题描述

我正在解决字符串问题的排列 - 给定两个字符串 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;
    }

标签： carraysstringalgorithmhash

解决方案

基于数组的解决方案的运行时间为 O(n)，因为它对每个字符串循环一次。但是，您的解决方案的运行时间为 O(n*m)，其中 n 和 m 是两个字符串的长度。在 中for找到的循环内checkInclusion，您调用findSumwhich 有自己的for循环。

你实际上不需要findSum一遍又一遍地打电话。您可以减去每个字符的值。

推荐阅读