8000 Updated chapter String · YidaChen/leetcode@7611b95 · GitHub
[go: up one dir, main page]
Skip to content

Commit 7611b95

Browse files
soulmachinesoulmachine
committed
Updated chapter String
1 parent e7844ce commit 7611b95

File tree

1 file changed

+49
-41
lines changed

1 file changed

+49
-41
lines changed

‎C++/chapString.tex

+49-41
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ \subsubsection{代码}
3535
if (!::isalnum(*left)) ++left;
3636
else if (!::isalnum(*right)) --right;
3737
else if (*left != *right) return false;
38-
else{ left++, right--; }
38+
else { left++, right--; }
3939
}
4040
return true;
4141
}
@@ -69,29 +69,20 @@ \subsubsection{暴力匹配}
6969
// 暴力解法，时间复杂度O(N*M)，空间复杂度O(1)
7070
class Solution {
7171
public:
72-
char *strStr(const char *haystack, const char *needle) {
73-
// if needle is empty return the full string
74-
if (!*needle) return (char*) haystack;
75-
76-
const char *p1;
77-
const char *p2;
78-
const char *p1_advance = haystack;
79-
for (p2 = &needle[1]; *p2; ++p2) {
80-
p1_advance++; // advance p1_advance M-1 times
81-
}
82-
83-
for (p1 = haystack; *p1_advance; p1_advance++) {
84-
char *p1_old = (char*) p1;
85-
p2 = needle;
86-
while (*p1 && *p2 && *p1 == *p2) {
87-
p1++;
88-
p2++;
72+
int strStr(const string& haystack, const string& needle) {
73+
if (needle.empty()) return 0;
74+
75+
const int N = haystack.size() - needle.size() + 1;
76+
for (int i = 0; i < N; i++) {
77+
int j = i;
78+
int k = 0;
79+
while (j < haystack.size() && k < needle.size() && haystack[j] == needle[k]) {
80+
j++;
81+
k++;
8982
}
90-
if (!*p2) return p1_old;
91-
92-
p1 = p1_old + 1;
83+
if (k == needle.size()) return i;
9384
}
94-
return nullptr;
85+
return -1;
9586
}
9687
};
9788
\end{Code}
@@ -103,10 +94,8 @@ \subsubsection{KMP}
10394
// KMP，时间复杂度O(N+M)，空间复杂度O(M)
10495
class Solution {
10596
public:
106-
char *strStr(const char *haystack, const char *needle) {
107-
int pos = kmp(haystack, needle);
108-
if (pos == -1) return nullptr;
109-
else return (char*)haystack + pos;
97+
int strStr(const string& haystack, const string& needle) {
98+
return kmp(haystack.c_str(), needle.c_str());
11099
}
111100
private:
112101
/*
@@ -389,7 +378,7 @@ \subsubsection{动规}
389378
// 动规，时间复杂度O(n^2)，空间复杂度O(n^2)
390379
class Solution {
391380
public:
392-
string longestPalindrome(string s) {
381+
string longestPalindrome(const string& s) {
393382
const int n = s.size();
394383
bool f[n][n];
395384
fill_n(&f[0][0], n * n, false);
@@ -423,7 +412,7 @@ \subsubsection{Manacher’s Algorithm}
423412
// Transform S into T.
424413
// For example, S = "abba", T = "^#a#b#b#a#$".
425414
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
426-
string preProcess(string s) {
415+
string preProcess(const string& s) {
427416
int n = s.length();
428417
if (n == 0) return "^$";
429418
@@ -520,6 +509,10 @@ \subsubsection{递归版}
520509
// 递归版，时间复杂度O(n)，空间复杂度O(1)
521510
class Solution {
522511
public:
512+
bool isMatch(const string& s, const string& p) {
513+
return isMatch(s.c_str(), p.c_str());
514+
}
515+
private:
523516
bool isMatch(const char *s, const char *p) {
524517
if (*p == '\0') return *s == '\0';
525518
@@ -596,6 +589,10 @@ \subsubsection{递归版}
596589
// 时间复杂度O(n!*m!)，空间复杂度O(n)
597590
class Solution {
598591
public:
592+
bool isMatch(const string& s, const string& p) {
593+
return isMatch(s.c_str(), p.c_str());
594+
}
595+
private:
599596
bool isMatch(const char *s, const char *p) {
600597
if (*p == '*') {
601598
while (*p == '*') ++p; //skip continuous '*'
@@ -618,6 +615,10 @@ \subsubsection{迭代版}
618615
// 迭代版，时间复杂度O(n*m)，空间复杂度O(1)
619616
class Solution {
620617
public:
618+
bool isMatch(const string& s, const string& p) {
619+
return isMatch(s.c_str(), p.c_str());
620+
}
621+
private:
621622
bool isMatch(const char *s, const char *p) {
622623
bool star = false;
623624
const char *str, *ptr;
@@ -751,7 +752,7 @@ \subsubsection{有限自动机}
751752
// finite automata，时间复杂度O(n)，空间复杂度O(n)
752753
class Solution {
753754
public:
754-
bool isNumber(const char *s) {
755+
bool isNumber(const string& s) {
755756
enum InputType {
756757
INVALID, // 0
757758
SPACE, // 1
@@ -774,17 +775,17 @@ \subsubsection{有限自动机}
774775
};
775776
776777
int state = 0;
777-
for (; *s != '\0'; ++s) {
778+
for (auto ch : s) {
778779
InputType inputType = INVALID;
779-
if (isspace(*s))
780+
if (isspace(ch))
780781
inputType = SPACE;
781-
else if (*s == '+' || *s == '-')
782+
else if (ch == '+' || ch == '-')
782783
inputType = SIGN;
783-
else if (isdigit(*s))
784+
else if (isdigit(ch))
784785
inputType = DIGIT;
785-
else if (*s == '.')
786+
else if (ch == '.')
786787
inputType = DOT;
787-
else if (*s == 'e' || *s == 'E')
788+
else if (ch == 'e' || ch == 'E')
788789
inputType = EXPONENT;
789790
790791
// Get next state from current state and input symbol
@@ -809,6 +810,10 @@ \subsubsection{使用strtod()}
809810
// 偷懒，直接用 strtod()，时间复杂度O(n)
810811
class Solution {
811812
public:
813+
bool isNumber (const string& s) {
814+
return isNumber(s.c_str());
815+
}
816+
private:
812817
bool isNumber (char const* s) {
813818
char* endptr;
814819
strtod (s, &endptr);
@@ -909,7 +914,7 @@ \subsubsection{代码}
909914
}
910915
}
911916
912-
int romanToInt(string s) {
917+
int romanToInt(const string& s) {
913918
int result = 0;
914919
for (size_t i = 0; i < s.size(); i++) {
915920
if (i > 0 && map(s[i]) > map(s[i - 1])) {
@@ -1070,7 +1075,7 @@ \subsubsection{代码}
10701075
// 时间复杂度O(n)，空间复杂度O(n)
10711076
class Solution {
10721077
public:
1073-
string simplifyPath(string const& path) {
1078+
string simplifyPath(const string& path) {
10741079
vector<string> dirs; // 当做栈
10751080
10761081
for (auto i = path.begin(); i != path.end();) {
@@ -1137,10 +1142,9 @@ \subsubsection{用 STL}
11371142
// 时间复杂度O(n)，空间复杂度O(1)
11381143
class Solution {
11391144
public:
1140-
int lengthOfLastWord(const char *s) {
1141-
const string str(s);
1142-
auto first = find_if(str.rbegin(), str.rend(), ::isalpha);
1143-
auto last = find_if_not(first, str.rend(), ::isalpha);
1145+
int lengthOfLastWord(const string& s) {
1146+
auto first = find_if(s.rbegin(), s.rend(), ::isalpha);
1147+
auto last = find_if_not(first, s.rend(), ::isalpha);
11441148
return distance(first, last);
11451149
}
11461150
};
@@ -1154,6 +1158,10 @@ \subsubsection{顺序扫描}
11541158
// 时间复杂度O(n)，空间复杂度O(1)
11551159
class Solution {
11561160
public:
1161+
int lengthOfLastWord(const string& s) {
1162+
return lengthOfLastWord(s.c_str());
1163+
}
1164+
private:
11571165
int lengthOfLastWord(const char *s) {
11581166
int len = 0;
11591167
while (*s) {

0 commit comments

Comments
 (0)
0