Joyce' Blog
0%

大锤的自动校对程序

发表于 更新于

题目描述

发现拼写错误的捷径：

  1. 三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello

  2. 两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello

  3. 上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC

实现大锤的自动校对程序。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string correct(int n,string s)
{
	int len = s.length();
	if (len<3)
	{
		return s;
	}
	int i = 0, j = 0;
	while (i<len)
	{
		s[j++] = s[i];
		if (j > 2 && s[j - 1] == s[j - 2] && s[j - 2] == s[j - 3])
			j--;
		if (j > 3 && s[j - 1] == s[j - 2] && s[j - 4] == s[j - 3])
			j--;
		i++;
	}
	s.erase(j);
	return s;
}

使用两个指针，快指针去遍历字符串，慢指针负责检查前面的位置是否出现错误的情况，如果有的话就后退一个位置。注意判断的时候要从j-1开始而不是j，因为s[j++]已经使j+1了。