利用空间换时间减少时间复杂度以及以C语言字符串处理为例减少空间复杂度

在处理字符串的过程当中，通常情况下都会逐个遍历整个字符串数组，在多个字符串的处理中，处理不同，时间复杂度不同，这里通过利用空间换时间等不同方法，以字符串处理为例来讨论几种情况：

1：空间换时间，减少时间复杂度

写一个函数返回bool值，来判断给定的字符串A和B（假设都是小写字母），
是否是B中的字符都存在于A中，如果是返回true，否则返回false
例如：A="ababcdeabcdef";B="aabbccef"->返回true;
A="abcabcdefaij";B="#bbcxaab";->返回false;


由上图可以看到：
B1字符都存在于A1字符串中，而B2中的字符x不存在与A2中， 通常第一思路都会对字符串进行遍历，取B中的一个字符和A 中的字符进行对比，最坏的情况下需要每遍历一次B后，再从头到尾遍历A中的字符，判断是否相同，时间复杂度为O（n^2）。
为了减少时间复杂度，算法思想：利用空间换时间来减少时间复杂度，这里利用一个数组来保存A中出现的字母，将a,b,c,d等记录在0,1,2,3，…下标下，而’a’-‘a’=0 , ‘b’-‘a’=1 , … , ‘z’-‘a’=25，恰好对应数组的下标0~25。因此通过 *A-‘a’ 将A中字符记录到数组中，之后遍历B中的字符是否出现在chars中，不出现返回false，出现继续向后遍历，直到跳出循环。

//代码
bool CheckString(const char *A,const char *B)//A >= B
{
int chars[26] = {0};
//登记A中出现的字母,a登记在0下标,b登记在1下标,c登记在2下标...z登记在25下标
//'a'-'a'=0,'b'-'a'=1,'z'-'a'=25->*A-'a'

while(*A != '\0')//遍历A,登记所有的字母
{
chars[*A - 'a']++;//哈希表,散列表
A++;
}

while(*B != '\0')//遍历B,查看B中所有字符是否出现在chars中
{
if(chars[*B-'a'] == 0)//*B字母没有出现在A中
{
return false;
}
B++;
}

return true;
}
int main()
{
char str1[]="ababcdeabcdef"; //测试用例
char str2[]="aabbccef";
char str3[]="abcabcdefaij";
char str4[]="#bbcxaab";
printf("%d\n",CheckString(str1,str2));
printf("%d\n",CheckString(str3,str4));

return 0;
}


2：减少空间复杂度（1）

给定一个字符串，其由空格和小写字母组成，要求删除多个空格，只留一个空格。
例如：char str1[] = "a b c hi j k";-->"a b c hi j k"
char str2[] = "m n pq f g k"; -->"m n pq f g k"


思想1：动态分配一个数组用来保存字符串，定义i, j其中初始j=i,从头遍历数组，将字母复制到申请的数组buf中，当当前字符跟下一个字符都为空时，不复制，当当前字符为空，下一个字符不为空时，复制，直到遍历结束，最后将buf中元素拷贝到str中。
（Blank1） 时间复杂度为O（n）,空间复杂度为O（n）
思想2：在原数组中进行，不申请内存，减少空间复杂度。定义i, j其中初始j=i,从头遍历数组，当当前字符跟下一个字符都为空时，不复制，当当前字符为空，下一个字符不为空时，复制，直到遍历结束，以‘\0’结尾。
（Blank2） 时间复杂度为O（n）,空间复杂度为O（1）


//1：删除多余空格，只保留一个空格
void Blank1(char *str)//时间复杂度：O(n) 空间复杂度：O(n)
{
int len=strlen(str);
char *buf=(char*)malloc(sizeof(char)*(len+1)); //动态分配一个数组
int i=0;
int j=0;
while(str[i]!='\0') //从头到尾遍历字符串
{
// 当当前字符跟下一个字符都为空格时，不复制，继续向后遍历
if(str[i]==' '&& str[i+1]==' ');
{
i++;
}
else //当前字符为空，下一个字符不为空格时，复制
{
buf[j++]=str[i++]; //将当前字符附给buf, i,j向后遍历
}
}
buf[j]='\0'; //buf后以'\0'结尾
strcpy(str,buf); //将buf中的元素拷贝给str
free(buf); //释放内存
}
void Blank2(char *str)//时间复杂度：O(n),空间复杂度：O(1)
{
int i =0;
int j = 0;
while(str[i]!='\0')
{
if(str[i]==' '&&str[i+1]==' ')
{
i++;
}
else
{
str[j++] = str[i++];
}
}
str[j] = '\0';
}
int main()
{
char str1[] = "a b c hi j k";
char str2[] = "m n pq f g k";
Blank1(str1);
printf("%s\n",str1);
Blank2(str2);
printf("%s\n",str2);
return 0;
}


减少空间复杂度（2）

将给定字符串中的*前移
例如：char str[] = "au**toc**h**i*ps";-->"*******autochips"


思想1：同样动态分配一个数组，定义一个指针，指向原数组的末尾，定义i从后往前遍历原数组，当遇到字母（非*）时,从buf的末尾开始向前复制字母，每复制一个，指针向前移动一个单元格，遍历完成后，将 （*）复制到 字母的前面，再将buf中元素拷贝到原数组str中。
（Str1） 时间复杂度为O（n）,空间复杂度为O（n）
思想2：同（1）中的在原数组中进行。定义i，j, 临时变量， i等于数组的最后一个下标值，j为i的前一个下标值，从后往前遍历，找第一个非字母(※)，没有找到直接跳出循环。找到时，将交换str[i]与str[j]的值即可。
（Str2） 时间复杂度为O（n）,空间复杂度为O（1）

//3：字符串中*前移
void Str1(char *str)//O(n),O(n)
{
int len = strlen(str);
char *buf = (char *)malloc((len+1)*sizeof(char));
buf[len] = '\0';
int i;
char *p = str;
while(*p != '\0')
p++;
p--;
for(i=len-1;p>=str;p--)//从后往前拷贝非*
{
if(*p != '*')
{
buf[i--] = *p;
}
}
while(i >= 0)
{
buf[i--] = '*';
}
strcpy(str,buf);
free(buf);
}
void Str2(char *str)//O(n),O(1)
{
int i = strlen(str) - 1;
int j = i;
char tmp;
while(i>=0 && j>=0)
{
//i找到右边第一个*
while(i>=0 && str[i] != '*')
{
i--;
}
if(i <0)
{
break;
}
j = i-1;
while(j>=0 && str[j] == '*')
{
j--;
}
if(j <0)
{
break;
}
tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
}
int main()
{
char str[] = "au**toc**h**i*ps";
Str1(str);
printf("%s\n",str);
Str2(str);
printf("%s\n",str);
return 0;
}


减少空间复杂度（3）

将给定字符串中的空格替换成% 2 0三个字符
例如：char str[100] = "a b cd e";-->"a%20b%20%20cd"


思想1：先统计字符串中空格的个数，动态分配一个长度为len+2*count+1的数组，遍历数组，将字母复制到buf中，当遇到空格时，分别将% 2 0复制到buf对应的下标中，直到结束，将buf中的元素拷贝到str中即可。

Replace1时间复杂度为O（n）,空间复杂度为O（n）
思想2：同样在原数组中进行操作，统计空格的个数，将最后的’\0’向后移动len*2个位置，这里保证能够将% 2 0 放在数组中，防止覆盖其他字符。从后往前开始遍历，当遇到空格时将% 2 0复制到数组中，字母同样放在相应的位置，直到结束。
Replace2时间复杂度为O（n）,空间复杂度为O（1）

//2：空格替换成%20
void Replace1(char *str)//O(n) O(n)
{
int len = strlen(str);
int count = 0;
int i = 0;
int j = 0;
for(i=0;str[i]!='\0';i++)
{
if(str[i]== ' ')
{
count++;
}
}
char *buf = (char *)malloc((len+2*count+1)*sizeof(char));
j = 0;
for(i=0;str[i]!= '\0';i++)
{
if(str[i] != ' ')
{
buf[j++] = str[i];
}
else//空格
{
buf[j++] = '%';
buf[j++] = '2';
buf[j++] = '0';
}
}
buf[j] = '\0';
strcpy(str,buf);
free(buf);
}
void Replace2(char *str)//O(n),O(1)
{
int i = strlen(str);//字符串末尾"\0"下标
int j;
int count = 0;
for(j=0;str[j]!='\0';j++)
{
if(str[j] == ' ')
{
count++;
}
}
j = i+count*2;
while(i >= 0)
{
if(str[i] != ' ')
{
str[j--] = str[i--];
}
else
{
str[j--] = '0';
str[j--] = '2';
str[j--] = '%';
i--;
}
}
}
int main()
{

char str[100] = "a b cd e";
Replace1(str);
printf("%s\n",str);
Replace2(str);
printf("%s\n",str);
return 0;
}


#include
#include
#include
#include


以上的减少空间复杂度的算法思想大致相同。通过在当前数组中进行，遍历数组对字符串处理。
代码可运行，有不妥之处还需指教。