数据结构与算法再探（二）串
目录
字符串比较：
C++实现
python3
验证回文串
C++实现
python3实现
最长回文串
C++实现
python3
反转单词
C++实现
python
字符串可以看作是字符组成的数组,字符串的常见操作有很多，搜索、匹配。
字符串比较：
1、有效的字母异位词：比较两个字符串s和t 是否是的字母异位词（若s 和t 中每个字符出现的次数都相同，则称s 和t 互为字母异位词) 输入: s = "anagram", t = "nagaram" 输出: true
242. 有效的字母异位词 - 力扣（LeetCode）
C++实现
class Solution
{
public:
bool isAnagram(string s, string t)
{
vector<int> count(26, 0);
if (s.length() != t.length())
{
return false;
}
for (int i = 0; i < s.size(); i++)
{
++count[s[i] - 'a'];
--count[t[i] - 'a'];
}
for (auto c : count)
{
if (c)
return false;
}
return true;
}
};
int main()
{
string s, t;
cin >> s >> t;
std::shared_ptr<Solution> mp = std::make_shared<Solution>();
cout << (mp->isAnagram(s, t) ? "true" : "false");
return 0;
}字符串比较这里默认字符串是26个字符，然后使用vector计算字符串对应位置如果出现+1，t字符串出现就-1，最后如果结果为0，说明两个字符串同样字符出现抵消。可以判定是否是字母异位词。
也可以使用array<int, 26> cnt_s{}, cnt_t{}; 分别统计字符，std::array可以直接使用==比较。
python3
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)验证回文串
将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，检测是否是回文串
125. 验证回文串 - 力扣（LeetCode）
C++实现
bool isPalindrome(string s) {
string t;
for(auto c :s){
if(islower(c)||isdigit(c)){ //检索出小写字母和数字字符
t+=c;
}else{
if(isupper(c)) //大写转小写
t+=(c+32);
}
}
int i=0,j=t.size()-1;
while (i<j){ //左右指针回文串判断
if(t[i++]!=t[j--])
return false;
}
return true;
}python3实现
def isPalindrome(self, s: str) -> bool:
#isalnum 判断字符串是否只包含字母和数字
#filter函数接收一个函数和可迭代对象，保留使函数为true的元素结果也是可迭代对象
#.join()是一个字符串方法用于将序列中的元素以指定的字符（或字符串）连接成一个新的字符串
s = ''.join(filter(str.isalnum, s.lower()))
return s == s[::-1] #切片反向遍历最长回文串
5. 最长回文子串 - 力扣（LeetCode）
C++实现
string longestPalindrome(string s)
{
string rev = s;
reverse(rev.begin(), rev.end()); #反转字符串
if (rev == s)
return s;
string res;
int len = 0;
for (int i = 0; i < s.length(); ++i)
{
string temp;
for (int j = i; j < s.length(); ++j)
{
temp += s[j];
if (len > temp.length()) #新检测的字符串小于目前最长的不需要后续比较
continue;
else if (rev.find(temp) != -1) #它与它反转后的字符串,其实是完全匹配的所以求公共串
{
string q = temp; #公共串也不一定是回文串如"aacabdkacaa" acaa最长却不是回文
reverse(q.begin(), q.end());
if (q == temp)
{
len = temp.size();
res = temp;
}
}
else
break;
}
temp = "";
}
return res;
}python3
def longestPalindrome(self, s: str) -> str:
lens = len(s)
if s == s[::-1] or len(s) == 1: #后面的滑动去字符判断就可以不用首尾再次判断
return s
for i in range(1,lens-1):
for j in range(i+1):
substr = s[j:lens-i+j] #左闭右开
if substr == substr[::-1]:
return substr
return s[0]反转单词
字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格
151. 反转字符串中的单词
C++实现
string reverseWords(string s) {
int n = s.size();
string res = "";
int i=0;
while(i<n) {
if (i != 0) {
res = " " + res; //反转之后的单词需要使用空格隔开
}
while (s[i] == ' ') { //排除多个空格找到非空格
++i;
if (i >= n)
break;
}
string temp = ""; //保存单词
while (s[i] != ' ') {
temp += s[i++];
if(i>=n)
break;
}
res = temp + res; //结果字符串
while (s[i] == ' ') {
i++;
}
}
return res;
}python
def reverseWords(self, s: str) -> str:
return " ".join(s.split()[::-1]) #split()去空格得list -1逆序字符串list，join空格获取字符串