Skip to content

Commit 5774145

Browse files
billryanbillryan
committed
split into two separate sections
1 parent ccd830e commit 5774145

3 files changed

Lines changed: 107 additions & 105 deletions

File tree

‎SUMMARY.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,7 @@
5454
* [Rotate String](reverse/rotate_string.md)
5555
* [Reverse Words in a String](reverse/reverse_words_in_a_string.md)
5656
* [String - 字符串](string/README.md)
57+
* [strStr](string/strstr.md)
5758
* [Compare Strings](string/compare_strings.md)
5859
* [Binary Tree - 二叉树](binary_tree/README.md)
5960
* [Binary Tree Preorder Traversal](binary_tree/binary_tree_preorder_traversal.md)

‎string/compare_strings.md‎

Lines changed: 2 additions & 105 deletions
Original file line numberDiff line numberDiff line change
@@ -1,107 +1,4 @@
1-
# Compare Strings - 字符串查找
2-
3-
## strstr
4-
5-
## Source
6-
7-
- lintcode: [lintcode - (13) strstr](http://www.lintcode.com/zh-cn/problem/strstr/)
8-
9-
```
10-
strstr (a.k.a find sub string), is a useful function in string operation. You task is to implement this function.
11-
12-
For a given source string and a target string, you should output the "first" index(from 0) of target string in source string.
13-
14-
If target is not exist in source, just return -1.
15-
16-
Example
17-
If source="source" and target="target", return -1.
18-
19-
If source="abcdabcdefg" and target="bcd", return 1.
20-
21-
Challenge
22-
O(n) time.
23-
24-
Clarification
25-
Do I need to implement KMP Algorithm in an interview?
26-
27-
- Not necessary. When this problem occurs in an interview, the interviewer just want to test your basic implementation ability.
28-
```
29-
30-
## 题解
31-
32-
对于字符串查找问题，可使用双重for循环解决，效率更高的则为KMP算法。
33-
34-
### Java
35-
36-
```java
37-
/**
38-
* http://www.jiuzhang.com//solutions/implement-strstr
39-
*/
40-
class Solution {
41-
/**
42-
* Returns a index to the first occurrence of target in source,
43-
* or -1 if target is not part of source.
44-
* @param source string to be scanned.
45-
* @param target string containing the sequence of characters to match.
46-
*/
47-
public int strStr(String source, String target) {
48-
if (source == null || target == null) {
49-
return -1;
50-
}
51-
52-
int i, j;
53-
for (i = 0; i < source.length() - target.length() + 1; i++) {
54-
for (j = 0; j < target.length(); j++) {
55-
if (source.charAt(i + j) != target.charAt(j)) {
56-
break;
57-
} //if
58-
} //for j
59-
if (j == target.length()) {
60-
return i;
61-
}
62-
} //for i
63-
64-
// did not find the target
65-
return -1;
66-
}
67-
}
68-
```
69-
70-
### 源码分析
71-
72-
1. 边界检查：`source`和`target`有可能是空串。
73-
2. 边界检查之下标溢出：注意变量`i`的循环判断条件，如果是单纯的`i < source.length()`则在后面的`source.charAt(i + j)`时有可能溢出。
74-
2. 代码风格：（1）运算符`==`两边应加空格；（2）变量名不要起`s1``s2`这类，要有意义，如`target``source`；（3）即使if语句中只有一句话也要加大括号，即`{return -1;}`；（4）Java 代码的大括号一般在同一行右边，C++ 代码的大括号一般另起一行；（5）`int i, j;`声明前有一行空格，是好的代码风格。
75-
3. 不要在for的条件中声明`i`,`j`，容易在循环外再使用时造成编译错误，错误代码示例：
76-
77-
### Another Similar Question
78-
79-
```java
80-
/**
81-
* http://www.jiuzhang.com//solutions/implement-strstr
82-
*/
83-
public class Solution {
84-
public String strStr(String haystack, String needle) {
85-
if(haystack == null || needle == null) {
86-
return null;
87-
}
88-
int i, j;
89-
for(i = 0; i < haystack.length() - needle.length() + 1; i++) {
90-
for(j = 0; j < needle.length(); j++) {
91-
if(haystack.charAt(i + j) != needle.charAt(j)) {
92-
break;
93-
}
94-
}
95-
if(j == needle.length()) {
96-
return haystack.substring(i);
97-
}
98-
}
99-
return null;
100-
}
101-
}
102-
```
103-
104-
## Compare Strings
1+
# Compare Strings
1052

1063
## Source
1074

@@ -164,7 +61,7 @@ public:
16461
};
16562
```
16663

167-
#### 源码解析
64+
### 源码解析
16865

16966
使用数组`freqA`和`freqB`分别保存A和B中各字母出现的频次，随后遍历比较两数组，若A中相应的频次小于B时，返回false，否则遍历完后返回true.
17067

‎string/strstr.md‎

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
# strStr
2+
3+
## Source
4+
5+
- leetcode: [Implement strStr() | LeetCode OJ](https://leetcode.com/problems/implement-strstr/)
6+
- lintcode: [lintcode - (13) strstr](http://www.lintcode.com/zh-cn/problem/strstr/)
7+
8+
```
9+
strstr (a.k.a find sub string), is a useful function in string operation.
10+
You task is to implement this function.
11+
12+
For a given source string and a target string,
13+
you should output the "first" index(from 0) of target string in source string.
14+
15+
If target is not exist in source, just return -1.
16+
17+
Example
18+
If source="source" and target="target", return -1.
19+
20+
If source="abcdabcdefg" and target="bcd", return 1.
21+
22+
Challenge
23+
O(n) time.
24+
25+
Clarification
26+
Do I need to implement KMP Algorithm in an interview?
27+
28+
- Not necessary. When this problem occurs in an interview,
29+
the interviewer just want to test your basic implementation ability.
30+
```
31+
32+
## 题解
33+
34+
对于字符串查找问题，可使用双重for循环解决，效率更高的则为KMP算法。
35+
36+
### Java
37+
38+
```java
39+
/**
40+
* http://www.jiuzhang.com//solutions/implement-strstr
41+
*/
42+
class Solution {
43+
/**
44+
* Returns a index to the first occurrence of target in source,
45+
* or -1 if target is not part of source.
46+
* @param source string to be scanned.
47+
* @param target string containing the sequence of characters to match.
48+
*/
49+
public int strStr(String source, String target) {
50+
if (source == null || target == null) {
51+
return -1;
52+
}
53+
54+
int i, j;
55+
for (i = 0; i < source.length() - target.length() + 1; i++) {
56+
for (j = 0; j < target.length(); j++) {
57+
if (source.charAt(i + j) != target.charAt(j)) {
58+
break;
59+
} //if
60+
} //for j
61+
if (j == target.length()) {
62+
return i;
63+
}
64+
} //for i
65+
66+
// did not find the target
67+
return -1;
68+
}
69+
}
70+
```
71+
72+
### 源码分析
73+
74+
1. 边界检查：`source`和`target`有可能是空串。
75+
2. 边界检查之下标溢出：注意变量`i`的循环判断条件，如果是单纯的`i < source.length()`则在后面的`source.charAt(i + j)`时有可能溢出。
76+
2. 代码风格：（1）运算符`==`两边应加空格；（2）变量名不要起`s1``s2`这类，要有意义，如`target``source`；（3）即使if语句中只有一句话也要加大括号，即`{return -1;}`；（4）Java 代码的大括号一般在同一行右边，C++ 代码的大括号一般另起一行；（5）`int i, j;`声明前有一行空格，是好的代码风格。
77+
3. 不要在for的条件中声明`i`,`j`，容易在循环外再使用时造成编译错误，错误代码示例：
78+
79+
## Another Similar Question
80+
81+
```java
82+
/**
83+
* http://www.jiuzhang.com//solutions/implement-strstr
84+
*/
85+
public class Solution {
86+
public String strStr(String haystack, String needle) {
87+
if(haystack == null || needle == null) {
88+
return null;
89+
}
90+
int i, j;
91+
for(i = 0; i < haystack.length() - needle.length() + 1; i++) {
92+
for(j = 0; j < needle.length(); j++) {
93+
if(haystack.charAt(i + j) != needle.charAt(j)) {
94+
break;
95+
}
96+
}
97+
if(j == needle.length()) {
98+
return haystack.substring(i);
99+
}
100+
}
101+
return null;
102+
}
103+
}
104+
```

0 commit comments

Comments
 (0)