字符串问题
字符串问题
单词拆分
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
bool wordBreak(string &s, vector<string> &dict) {
int n= s.length();
if(n == 0) return true;
if(dict.size() == 0) return false;
vector<bool> res(n+1,false);
res[0] = true;
//时间复杂度是O(n*m)
for(int i=1; i<=n; i++)
{
for(int k=0; k<dict.size(); ++k)
{
int j = dict[k].size(); //从0开始找s的子结构，看是否在dict中
if(i<j) continue;
if(dict[k] == s.substr(i-j,j)) //取当前的s子结构
{
if(res[i-j])
{
res[i] = true;
}
}
}
}
return res[n];
}
单词拆分2
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:[ "cats and dog", "cat sand dog"]
思路：dfs，回溯
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<string> res;
string out;
vector<bool> possible(s.size() + 1, true);
wordBreakDFS(s, wordDict, 0, possible, out, res);
return res;
}
void wordBreakDFS(string &s, unordered_set<string> &wordDict, int start, vector<bool> &possible, string &out, vector<string> &res) {
if (start == s.size()) {
res.push_back(out.substr(0, out.size() - 1));
return;
}
for (int i = start; i < s.size(); ++i) {
string word = s.substr(start, i - start + 1);
if (wordDict.find(word) != wordDict.end() && possible[i + 1]) {
out.append(word).append(" ");
int oldSize = res.size();
wordBreakDFS(s, wordDict, i + 1, possible, out, res);
if (res.size() == oldSize) possible[i + 1] = false;
out.resize(out.size() - word.size() - 1); //s.resize(100); // 相当于 new char[100];
}
}
}
字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
思路：这道题不能用全排列的思路来做，否则一定会出现超时的情况，我们需要两个长度为26的哈希表memo1和memo2，用来记录s1和s2中每个字符出现的次数，我们维护一个长度为s1.size()的滑动窗口，逐渐从0到s2.size()滑动，如果滑动窗口内的memo2累计的在窗口内的各个字符对应次数等于memo1，那么返回true，否则返回false
bool checkInclusion(string s1, string s2) {
if (s1.size() > s2.size()) return false;
vector<int> memo1(26, 0);
vector<int> memo2(26, 0);
for (int i = 0; i < s1.size(); i++) {
memo1[s1[i] - 'a']++;
}
for (int i = 0; i < s2.size(); i++) {
if(i<s1.size()) memo2[s2[i] - 'a']++;
else {
memo2[s2[i] - 'a']++;
memo2[s2[i-s1.size()] - 'a']--;
}
if (memo1 == memo2) return true;
}
return false;
}
翻转字符串里的单词
输入: "the sky is blue",
输出: "blue is sky the".
思路：先把字符串整个反转，然后找第一个空格的地方，然后，反转开始到空格的地方
void reverseWords(string &s) {
int storeIndex = 0, n = s.size();
reverse(s.begin(), s.end());
for (int i = 0; i < n; ++i) {
if (s[i] != ' ') {
if (storeIndex != 0) s[storeIndex++] = ' ';
int j = i;
while (j < n && s[j] != ' ') s[storeIndex++] = s[j++];
reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
i = j;
}
}
s.resize(storeIndex);
}
[翻转字符串2]
输入：["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出：["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
void reverseWords(vector<char>& str) {
reverse(str.begin(), str.end());
for (int i = 0, j = 0; i < str.size(); i = j + 1) {
for (j = i; j < str.size(); ++j) {
if (str[j] == ' ') break;
}
reverse(str.begin() + i, str.begin() + j);
}
}
[简化路径]
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
思路：主要是用到getline函数，每次读/之间的字母
#include <sstream>
string simplifyPath(string path) {
string res, t;
stringstream ss(path);
vector<string> v;
while (getline(ss, t, '/')) { //从ss中读，存到t中，/不读
if (t == "" || t == ".") continue;
if (t == ".." && !v.empty()) v.pop_back();
else if (t != "..") v.push_back(t);
}
for (string s : v) res += "/" + s;
return res.empty() ? "/" : res;
}
数字拼接最小值
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323
思路：数字m和n,两种拼接方式mn和nm,因为长度都一样，所以可以用比较字符串的方式比较他们的大小。用快速排序，得到的第一个字符串表示和其他字符串的组合，它都需要放在前面才能使得组合的数字更小，所以它在排序的结果中位于第一个
bool compare(const string& str1, const string& str2) {
return str1 + str2 < str2 + str1;
}
string PrintMinNumber(vector<int> numbers) {
vector<string> tb;
for (int i = 0; i < numbers.size(); i++) {
tb.push_back(to_string(numbers[i]));
}
sort(tb.begin(), tb.end(), compare);
string res = "";
for (int i = 0; i < tb.size(); i++) {
res += tb[i];
}
return res;
}
字符串翻转
这道题考的核心是是不是可以灵活利用字符串翻转。假设字符串abcdef，n=3，设X=abc，Y=def，所以字符串可以表示成XY，如题干，问如何求得YX。假设X的翻转为XT，XT=cba，同理YT=fed，那么YX=(XTYT)T，三次翻转后可得结果。
表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路:
E后面一定是数字并且不能同时出现两个E
不能出现两个小数点 并且小数点不能出现在E后面
如果符号第二次出现，则符号前面的字符一定是E (-1E-16)
如果符号是第一次出现并且不是在第一位，那么符号前面的字符也一定是E (5e+2)
bool isNumeric(char* string) {
bool sign=false, dot=false, hasE=false;
int i=0;
while(string[i]!='\0'){
if(string[i]=='e' || string[i]=='E'){
if(hasE || string[i+1]=='\0') return false;
hasE = true;
}else if(string[i]=='.'){
if(dot || hasE) return false;
dot = true;
}else if(string[i]=='+' || string[i]=='-'){
if(sign && string[i-1]!='E' && string[i-1]!='e') return false;
if(!sign && i>0 && string[i-1]!='E' && string[i-1]!='e') return false;
sign = true;
}else if(!isdigit(string[i])) return false;
i++;
}
return true;
}
字符串相乘
string multiply(string num1, string num2) {
string res;
int n1 = num1.size(), n2 = num2.size();
int k = n1 + n2 - 2, carry = 0;
vector<int> v(n1 + n2, 0);
for (int i = 0; i < n1; ++i) {
for (int j = 0; j < n2; ++j) {
v[k - i - j] += (num1[i] - '0') * (num2[j] - '0');
}
}
for (int i = 0; i < n1 + n2; ++i) {
v[i] += carry;
carry = v[i] / 10;
v[i] %= 10;
}
int i = n1 + n2 - 1;
while (v[i] == 0) --i;
if (i < 0) return "0";
while (i >= 0) res.push_back(v[i--] + '0');
return res;
}
