七日算法先导(七)——字符串
【摘要】 相关概念字符串:由零个或多个字符组成的有限序列。子串:一个串中任意个连续字符组成的子序列(含空串)称为该串的子串。真子串是不包含自身的所有子串。主串:包含子串的串相应的称为主串字符位置:字符在序列中的序号为该字符在串中的位置子串位置:子串第一个字符在主串中的位置空格串:由一个或多个空格组成的串(与空串不同)串相等:当且仅当两个串的长度相等并对应位置上的字符都相等时,这两个串才是相等的。所有...
相关概念
-
字符串:由零个或多个字符组成的有限序列。
-
子串:一个串中任意个连续字符组成的子序列(含空串)称为该串的子串。
真子串是不包含自身的所有子串。 -
主串:包含子串的串相应的称为主串
-
字符位置:字符在序列中的序号为该字符在串中的位置
-
子串位置:子串第一个字符在主串中的位置
-
空格串:由一个或多个空格组成的串(与空串不同)
-
串相等:当且仅当两个串的长度相等并对应位置上的字符都相等时,这两个串才是相等的。
所有空串是相等的。
回文串
字符串的基本概念上面俩篇文章都讲的很清楚了,其中还有一个回文串,我们现在来看一下:
回文串:一串正着读和反着读都是一样的一种特殊字符串
俩个方法:
- 直接函数反转
- 中心拓展方法
函数反转
对于每个语言函数api可能不同,我们统称为reverse函数
我们输入的字符串类型定位string型,然后使用reverse函数就可以,然后我们直接比较str1与str2是否相等,相等的话那么就表示输入的字符串为回文串。
reverse(str2.begin(), str2.end());
假设,题目中禁止了反转函数那么我们可以手写一个函数,也是比较容易实现的:
void reverse(char * str)
{
int len=strlen(str);
char *ch=str+len-1;
while(len>1)
{
char tmp=*str;
*str=*ch;
*ch='\0';
reverse(str+1);
*ch = tmp;
len--;
}
}
俩边向中心靠拢
比如对一个字符串 ababa,选择left = 0,和right = n-1,如果俩个相等,则left++,right–
当left与right俩个所指的数不等,则不是回文,直接退出,反之,left == right时候,就是回文串
class Solution {
public boolean isPalindrome(String s) {
int n = s.length();
int left = 0, right = n - 1;
//
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
++left;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
--right;
}
if (left < right) {
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
++left;
--right;
}
}
return true;
}
}
刷题巩固
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)