【算法|字符串、哈希表】验证回文串、螺旋塔、同构字符串、单词规律

目录

一、验证回文串

题目思路

解法一：

复杂度：

解法二：

复杂度：

二、螺旋塔

三、同构字符串

 四、单词规律

---

一、验证回文串

题目思路

该题是字符串相关，要求是移除给定字符串中的非字母字符和非数字字符，将大写字母字符转化为小写字母字符，在判断该字符串是否是回文串，下面有两种解法：

解法一：

定义一个string对象用于存储移除给定字符串中的非字母非数字，在对该string对象利用双指针进行判断。

复杂度：

时间复杂度：O(n)   空间复杂度：O(n)

class Solution {
public:bool isPalindrome(string s) {string str;int size = s.size();for(int i = 0;i < size;++i){if(s[i] >= 65 && s[i] <= 90){s[i] = s[i] + 32;}if(s[i] >= 97 && s[i] <= 122 || s[i] >= 48 && s[i] <= 57)//只将小写字母和数字字符push_back到str中str.push_back(s[i]);}int left = 0,right = str.size()-1;while(left < right){if(str[left] != str[right])return false;++left;--right;}return true;}
};

解法二：

对其对解法一的空间复杂度进行优化，不用定义string对象，直接在给定字符串上进行操作。

复杂度：

时间复杂度：O(n)    空间复杂度：O(1)

class Solution {
public:bool isPalindrome(string s) {int left = 0,right = s.size()-1;for(auto& ch:s) //将s中的大写字母转化为小写字母{if(ch >= 65 && ch <= 90)ch += 32;}while(left < right){while(left < right){if(s[left] >= 97 && s[left] <= 122 || s[left] >= 48 && s[left] <= 57)//这里数字字符'0'到'9'的ASCII范围是[48,90]break;else++left;}while(left < right){if(s[right] >= 97 && s[right] <= 122 || s[right] >= 48 && s[right] <= 57)break;else--right;}if(s[left++] != s[right--])return false;}return true;}
};

二、螺旋塔

给定一个字符串s和一个整数n，需要按照特定的规则构建并输出一个螺旋塔形状的字符串序列。

这个字符串仅由小写英文字母组成，它是构建螺旋塔的基础元素。而整数n则决定了螺旋塔的层数。

螺旋塔的构建规则如下：

螺旋塔的构建规则如下：

1.第一层是原始给定的字符串。

2.从第二层开始，每一层都是将上一层字符串的第一个字符移到末尾而形成的新字符串。

例如，对于字符串"abcd"：

第一层为"abcd"。

第二层，将第一层的第一个字符a移到末尾，得到"bcda"。

第三层，将第二层的第一个字符b移到末尾，得到"cdab"。

第四层，将第三层的第一个字符c移到末尾，得到"dabc"。

要求：

输入：第一行输入一个字符串s，它代表了构建螺旋塔的初始元素。第二行输入一个整数n，它确定了你要构建的螺旋塔的层数。

输出：输出螺旋塔的前n层字符串，每层占一行。

#include <iostream>
#include <string>
#include <vector>
using namespace std;void func(vector<string>& vv, int n)
{string s = vv[0];int index = 0;while (--n){string tmp = vv[index++];string::iterator it = tmp.begin();char ch = *it;tmp.erase(it);tmp.push_back(ch);vv.push_back(tmp);}for (const auto& e : vv){cout << e << endl;}
}
int main()
{string str;int n = 0;cin >> str;cin >> n;vector<string> vv;vv.push_back(str);func(vv, n);return 0;
}

三、同构字符串

class Solution {
public:bool isIsomorphic(string s, string t) {unordered_map<char,char> hashtable_1;unordered_map<char,char> hashtable_2;int size = s.size();for(int i = 0;i < size;++i){int ch_1 = s[i];int ch_2 = t[i];if(hashtable_1.count(ch_1) && hashtable_1[ch_1] != ch_2)return false;if(hashtable_2.count(ch_2) && hashtable_2[ch_2] != ch_1)return false;hashtable_1[ch_1] = ch_2;hashtable_2[ch_2] = ch_1;}return true;}
};

 四、单词规律

 

class Solution {
public:bool wordPattern(string pattern, string s) {vector<string> str;stringstream iss(s); //直接截取字符串的函数string word;while(iss>>word) str.push_back(word); //把字符串放入if(str.size()!=pattern.size()) return false; //判断是不是满射unordered_map<char,string>pw; //判断是不是单射unordered_map<string,char>wp; //判断是不是映射for(int i = 0;i<pattern.size();i++){auto a = pattern[i];auto b = str[i];if(pw.count(a)&&pw[a]!=b) return false; //如果存在该字母对应的字符串不一致，则返回falsepw[a] = b; //存入哈希表if(wp.count(b)&&wp[b]!=a) return false; //如果存在该字符串对应的单词有多个（不一致） ，返回falsewp[b] = a; //存入哈希表}return true;}
};