【经典算法】字符串旋转和包含算法

发表于 | 分类 | 阅读 次
字数: 1.9k | 时长 ≈ 8

本系列为《编程之法：面试和算法心得》的读书笔记。

作为一名大龄青年，为了即将踏入研究生之路，特此需要做一些计算机相关基础知识的积累，以弥补算法知识，谨以此开始自己的算法学习之路。

算法1.1：旋转字符串

  • 题目描述

    给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符’a’和’b’移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

  • 分析与解法

解法一：暴力移位法

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
28
29
// 算法1.1：旋转字符串，暴力移位法
void LeftShiftOne(char* strs, int number)
{	
	int i = 0;
	char ch = strs[i];
	for(i = 1; i < number; i++)
	{
		strs[i-1] = strs[i];
	}
	strs[i-1] = ch;
}


void LeftRoatateString(char* strs, int n, int m)
{
	while(m--)
	{
		LeftShiftOne(strs, n);
	}
}

// 测试函数
int main(int argc, char* argv[])
{	
	char strs[] = "ABCDEFGH";
	LeftRoatateString(strs, 8, 3);
	cout << strs << endl;
	return 0;
}

算法分析：针对长度为n的字符串而言，假设需要移动m个字符到字符串的尾部，总共需要移动 m*n 次操作，同时设立一个变量存储第一个字符，故时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$，不合题意。

解法二：三步反转法

思路分析：将一个字符串分成X和Y两部分，在每个部分字符串上定义反转操作，如$X^T$，即把X的所有字符反转（例如X=”abc”，则 $X^T$=”cba”），于是得到：$(X^T Y^T)^T$=$YX$。

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
28
// 算法1.1：旋转字符串，三步反转法
void ReverseString(char* str, int from, int to)
{
	while(from < to)
	{
		char ch = str[from];
		str[from++] = str[to];
		str[to--] = ch;
	}
}


void LeftReverseString(char* strs, int n, int m)
{
	m %= n;
	ReverseString(strs, 0, m-1);
	ReverseString(strs, m, n-1);
	ReverseString(strs, 0, n-1);
}

// 测试函数
int main(int argc, char* argv[])
{	
	char strs[] = "ABCDEFGH";
	LeftReverseString(strs, 8, 3);
	cout << strs << endl;
	return 0;
}

算法分析：针对长度为n的字符串而言，假设需要移动m个字符到字符串的尾部，总共需要移动 2*n 次操作，同时设立一个变量存储第一个字符，故时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，符合题意。

  • 练习题（自己动手）
  1. 链表翻转。例如给出一个链表和一个数k，链表为1—>2—>3—>4—>5—>6，k=2，则翻转后为2—>1—>6—>5—>4—>3；若k=3，翻转后3—>2—>1—>6—>5—>4。
  2. 编写程序在原来字符串中把字符串尾部的m个字符移动到字符串的头部，要求：长度为n的字符串操作时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。例如，源字符串为 “Ilovebaofeng”，m=7时输出为：“baofengIlove”。
  3. 单词翻转。输入一个英文句子，翻转句子中单词的顺序，但是单词内字符的顺序不变，句子中单词以空格符号隔开。为简单起见，标点符号和普通字符一样处理。例如，输入”I am a student.”，输出为 “student. a am I”。

算法1.2：字符串包含

  • 题目描述

    给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何快速地判断字符串B中的所有字符是否都在字符串A里面？
    为简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数 bool StringContain(string &A, string &B)。
    示例一：string 1：ABCD，string 2： BAD，答案为true；
    示例二：string 1：ABCD，string 2： BCE，答案为false；
    示例三：string 1：ABCD，string 2： AA，答案为true。

  • 分析与解法

解法一：常规解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 算法1.2：字符串包含，常规方法
bool StringContain(string &a, string &b)
{
	for(int i=0; i < b.length(); i++)
	{
		int j;
		for(j=0; (j < a.length()) && (a[j] != b[i]); j++);
		if(j >= a.length())
		{
			return false;
		}
	}
	return true;
}

// 测试函数
int main(int argc, char* argv[])
{	
	string a = "ABCD";
	string b = "AA";
	bool result = StringContain(a, b);
	cout << result << endl;
	return 0;
}

算法分析：这是一种最直观也是最简单的方法思路。此算法需要 $O（n*m）$ 次操作，时间开销较大。

解法二：排序方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 算法1.2：字符串包含，排序方法
bool StringContainSort(string &a, string &b)
{
	sort(a.begin(), a.end());   // 包含于<algorithm>模块内
	sort(b.begin(), b.end());
	for(int pa = 0, pb = 0; pb < b.length(); pb++)
	{
		while((pa < a.length()) && (a[pa] < b[pb]))
		{
			pa++;
		}
		if(pa >= a.length() || (a[pa] > b[pb]))
		{
			return false;
		}
	}
	return true;
}

算法分析：两个字符串的排序需要（常规情况）$O(m log m)+O(n log n)$ 次操作（快排算法），然后需要线性扫描 $O(m+n)$ 次操作。

解法三： 转换成素数

思路分析：

1）假定有一个仅由字母组成的字符串，按照从小到大的顺序，让每个字母与一个素数唯一对应，即用26个素数分别对应于A~Z；
2）遍历长字符串。求得每个字符对应素数的乘积；
3）遍历短字符串，判断乘积能否被短字符串中的字符对应的素数整除；
4）输出结果。

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
// 算法1.2：字符串包含，转换成素数
bool StringContainPrime(string &a, string &b)
{
	const int array[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
		43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
	int f = 1;
	for(int i = 0; i < a.length(); i++)
	{
		int x = array[a[i] - 'A'];
		if(f % x)
		{
			f *= x;
		}
	}
	
	for(int j = 0; j < b.length(); j++)
	{
		int x = array[b[j] - 'A'];
		if(f % x)
		{
			return false;
		}
	}
	return true;
}

算法分析：算法的时间复杂度为 $O(n)$ ，最好的情况为 $O(1)$（遍历短的字符串的第一个数，与长字符串素数的乘积相除，即出现余数，便可退出程序，返回 false）， n 为长字串的长度，空间复杂度为 $O(1)$。
注意：此方法只有理论意义，因为整数乘积很大会造成溢出风险。

解法四：Hashtable方法

思路分析：先把长字符串 A中的所有字符都放入一个 Hashtable 里，然后轮询短字符串 B，看短字符串 B 的每个字符是否都在 Hashtable 里，如果都存在，说明长字符串 A 包含短字符串 B， 否则，说明不包含。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 算法1.2：字符串包含，Hashtable方法
bool StringContainHash(string &a, string &b)
{
	int hash = 0;
	for(int i = 0; i < a.length(); i++)
	{
		hash |= (1 << (a[i] - 'A'));
	}
	
	for(int j = 0; j < b.length(); j++)
	{
		if(hash & (1 << (b[j] - 'A')))
		{
			return false;
		}
	}
	return true;
}

算法分析：此方法实质是用一个整数代替了Hashtable，空间复杂度为 $O(1)$，时间复杂度为 $O(n)$。

  • 练习题（自己动手）

变位词：如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，比如 bad 和 adb 即为兄弟字符串，现提供一个字符串，如何在字典中迅速找到它的兄弟字符串，请描述数据结构和查询过程。

坚持原创技术分享，您的支持将鼓励我继续创作！