首页 > 代码库 > 编程之美3.1 字符串移位包含问题
编程之美3.1 字符串移位包含问题
这道题目的意思是给定一个字符串,作为源字符串,之后给出其他的字符串,确定源字符串是否能够经过旋转而得到给定的字符串,即移位包含问题。
假如,给定一个字符串 abcdefg,接着给定字符串 cdefgab,很显然,给定的字符串是可以经过源字符串旋转而得到的,但是,给定字符串 cdegfab 就不能由源字符串经过旋转而得到。
当然,这道题有很多解法,我们可以经过判断字符串中字符的位置而得到答案,但是,那样做确实是太麻烦了,有更好的解法吗?当然,我们看下两个字符串的规律,当把源字符串 * 2 时,即拼接在一块,只要是给定字符串能经过源字符串旋转而得到,那么,给定的字符串一定在源字符串 * 2中。例如,前面的例子,把源字符串 * 2 ,可以得到的字符串是 abcdefgabcdefg,我们可以看到,给定的字符串确实是出现在其中的。
好了,有了上述思想,我们可以利用 strstr 函数求解这个问题了,strstr 函数是返回目的字符串出现在源字符串的位置,如果返回 NULL,那么就不存在,即不能经过源字符串旋转而得到。
函数声明:
bool DutShiftContains_1(char*, char*);
源代码:
bool DutShiftContains_1(char* str1, char* str2) { if (!str1 || !str2) return false; size_t len = strlen(str1); /*对原字符串进行拼接*/ char* _str1 = new char[2 * len + 1]; strcpy_s(_str1, 2 * len + 1, str1); strcat_s(_str1, 2 * len + 1, str1); bool result = strstr(_str1, str2) == NULL ? false : true; delete[] _str1; return result; }
现在,我们来思考书后的扩展,即不申请别的空间,能求解这个问题吗?因为,需要拼接字符串自然需要申请更多的空间。
答案是:可以。我们虚拟的来做,即当达到源字符串的末尾时,从源字符串的开头处比对不就行了吗。当然,这就是取余的方法了。
函数声明:
bool DutShiftContains_2(char*, char*);
源代码:
bool DutShiftContains_2(char* str1, char* str2) { if (!str1 || !str2) return false; size_t len1 = strlen(str1); size_t len2 = strlen(str2); if (len1 != len2) { return false; } /*模拟拼接处理*/ for (int i = 0; i != len1; ++i) { if (str1[i] == str2[0]) { int j = 1; while (str1[(i + j) % len1] == str2[j++]) { if (str2[j] == ‘\0‘) return true; } } } return false; }
编程之美3.1 字符串移位包含问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。