字符串
字符串是一个由字符构成的数组。
之后深入研究字符串，需要掌握如下知识点：
- 熟悉字符串中的基本操作，尤其是在数组中没有的独特操作；
- 理解不同比较函数之间的区别；
- 理解字符串是否可变以导致连接过程中出现的问题；
- 能够解决与字符串相关的基本问题，如排序、子串、字符串匹配等；
字符串简介
维基百科：字符串是由零个或多个字符组成的有限序列。一般记为 s = a1a2…an。它是编程语言中表示文本的数据类型。
为什么单独讨论字符串
虽然字符串与数组有很多的相似之处，但是还是要单独讨论字符串，为什么呢？原因有以下几点：
1.字符串的基本操作对象通常是字符串整体或者其中的子串
例如： I love you 你想将这个字符串反向输出，你肯定不想得到 uoy evol I 想得到的肯定是 you love I
维持单词本身的顺序可以让我们很方便的做其他的操作，这其中每个单词就被称为子串。
2.字符串操作要比其他数据类型更复杂（例如：比较、连接操作）
对于不同的编程语言，字符串的某些操作会有所不同。
下来继续撸代码了：
题目：最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串””。
示例：
1
2
3
4
5
| 输入: ["flower","flow","flight"]
输出: "fl"
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
|
说明:
所有输入只包含小写字母 a-z
个人理解：
公共前缀，直接一个一个往下比较即可，第一个比较第二个，用公共的前缀，再去和第三个比较。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
string res = strs[0];
int index = 1;
while(index < strs.size()){
string tmp = strs[index].substr(0, res.length());
if(tmp == res){
index++;
}else{
res = res.substr(0,res.length() - 1);
}
cout << index << endl;
}
return res;
}
};
|
题目：最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例：
1
2
3
4
5
6
| 输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
输入: "cbbd"
输出: "bb"
|
个人理解：
最开始觉得就暴力法就行，后来学了一下，了解到动态规划。这很合理。
如果一个字符串为回文串，那他去掉两边肯定还是回文串。这就得到了一个动态规划方程：
res[i][j] = res[i+1][j-1]; 一步一步判断就完了。
反正动态规划好理解，实现复杂点，不懂的话需要多看看。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
string longestPalindrome(string s) {
int len = s.size();
if(len <= 1) return s;
vector<vector<int>> res (len,vector<int>(len,0));
for(int i = 0; i < len; i++)res[i][i] = 1;
int start = 0;
int maxlength = 1;
for(int j = 1; j < len; j++){
for(int i = 0; i < j; i++){
if(s[i] == s[j]){
if(j-i < 3) res[i][j] = 1;
else res[i][j] = res[i+1][j-1];
}
if(res[i][j]){
if(j-i+1 > maxlength){
maxlength = j-i+1;
start = i;
}
}
}
}
return s.substr(start,maxlength);
}
};
|
题目：翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例：
1
2
3
4
5
6
7
8
9
10
| 输入: "the sky is blue"
输出: "blue is sky the"
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
|
说明：
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
个人理解：
这个我先想到的就是用栈，遇到空格就把单词推入栈中，最后再推出来，加上空格即可。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
string reverseWords(string s) {
int left = 0, right = s.size() - 1;
while(left <= right && s[left] == ' ') left++;
while(left <= right && s[right] == ' ') right--;
stack<string> st;
string word;
while(left <= right){
char c = s[left];
if(!word.empty() && c == ' '){
st.push(word);
word = "";
}else if(c != ' ') word += c;
left++;
}
st.push(word);
string ans;
while(!st.empty()){
ans += st.top();
st.pop();
if(!st.empty()) ans += ' ';
}
return ans;
}
};
|
题目：实现 strStr()
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置(从 0 开始)。如果不存在，则返回-1。
示例：
1
2
3
4
5
| 输入: haystack = "hello", needle = "ll"
输出: 2
输入: haystack = "aaaaa", needle = "bba"
输出: -1
|
说明:
- 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
- 对于本题而言，当 needle 是空字符串时我们应当返回 0。这与 C 语言的 strstr()以及 Java 的 indexOf()定义相符。
个人理解：
使用开窗法，用子串逐一比较，时间复杂度为线性。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int strStr(string haystack, string needle) {
int h_len = haystack.size(), n_len = needle.size();
if(n_len == 0) return 0;
if(n_len > h_len) return -1;
for(int i = 0; i < h_len - n_len + 1; i++){
if(haystack.substr(i,n_len) == needle) return i;
}
return -1;
}
};
|
声明：本文为学习记录，参考之处较多，如果有侵权内容，请联系我立即删除。
