Question 1: implement strStr()
Topic information
Implement the strStr() function.
Here are two strings: haystack and need. Please find the first position of the need string in the haystack string (the subscript starts from 0). If it does not exist, - 1 is returned.
explain:
When ， need ， is an empty string, what value should we return? This is a good question in the interview.
For this question, we should return 0 when {need} is an empty string. This is consistent with the definitions of {str() in C language and} indexOf() in Java.
Example 1:
Input: haystack = "hello", need = "ll"
Output: 2
Example 2:
Input: haystack = "AAAAA", need = "BBA"
Output: - 1
Example 3:
Input: haystack = "", need = ""
Output: 0
Tips:
0 <= haystack.length, needle.length <= 5 * 104
haystack and need consist of lowercase English characters only
Related labels
Double pointer
character string
string matching
Problem solving ideas
The first thought is of course the most violent solution. Traverse the haystack string. Whenever you read that the character is the same as the first character of the need, compare it with the need until the remaining length of the haystack is less than the need.
However, the time complexity of the algorithm is high, and there is still a lot of space to optimize
Here we introduce KPM algorithm
code
Violent solution
func strStr(haystack, needle string) int {
n, m := len(haystack), len(needle)
outer:
for i := 0; i+m <= n; i++ {
for j := range needle {
if haystack[i+j] != needle[j] {
continue outer
}
}
return i
}
return -1
}
Author: LeetCode-Solution
Link: https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.kmp algorithm
func strStr(haystack, needle string) int {
n, m := len(haystack), len(needle)
if m == 0 {
return 0
}
pi := make([]int, m)
for i, j := 1, 0; i < m; i++ {
for j > 0 && needle[i] != needle[j] {
j = pi[j-1]
}
if needle[i] == needle[j] {
j++
}
pi[i] = j
}
for i, j := 0, 0; i < n; i++ {
for j > 0 && haystack[i] != needle[j] {
j = pi[j-1]
}
if haystack[i] == needle[j] {
j++
}
if j == m {
return i - m + 1
}
}
return -1
}
Author: LeetCode-Solution
Link: https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.Complexity analysis
Violent solution
Complexity analysis
Time complexity: O(n) × m) Where n is the length of the string haystack and M is the length of the string need. In the worst case, we need to match the string need with all substrings of length m of the string haystack once.
Space complexity: O(1). We only need a constant space to hold several variables.
KMP solution
Complexity analysis
Time complexity: O(n+m), where n is the length of the string haystack and M is the length of the string need. We need to traverse the string at most once.
Spatial complexity: O(m), where m is the length of the string need. We only need to save the prefix function of the string need.
Operation results
We can see
KPM algorithm greatly optimizes the time complexity
Question 2 appearance sequence
Topic information
Given a positive integer n, the nth item of the appearance sequence is output.
"Appearance sequence" is a sequence of integers. Starting from the number 1, each item in the sequence is a description of the previous item.
You can think of it as a sequence of numeric strings defined by recursive formulas:
countAndSay(1) = "1"
countAndSay(n) is a description of countAndSay(n-1), which is then converted to another numeric string.
The first five items are as follows:
- 1
- 11
- 21
- 1211
- 111221
The first item is the number 1
Describe the former item. This number is 1, that is, "a 1", which is recorded as "11"
Describe the former item. The number is 11, that is, "two 1s", which is recorded as "21"
Describe the former item. The number is 21, that is, "one 2 + one 1", which is recorded as "1211"
Describe the former item. The number is 1211, that is, "one 1 + one 2 + two 1", which is recorded as "111221"
To describe a numeric string, first divide the string into a minimum number of groups, each consisting of a continuous maximum of the same characters. Then, for each group, first describe the number of characters, and then describe the characters to form a description group. To convert a description to a numeric string, replace the number of characters in each group with numbers, and then connect all description groups.
For example, the digital string "3322251" is described as follows:
Example 1:
Input: n = 1
Output: "1"
Explanation: This is a basic example.
Example 2:
Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = read "1" = a 1 = "11"
countAndSay(3) = read "11" = two 1 = "21"
countAndSay(4) = read "21" = one 2 + one 1 = "12" + "11" = "1211"
Tips:
1 <= n <= 30
Problem solving ideas
Simply a recursive function to solve the problem
Write a function to find item n, and the parameter is the string returned by item n-1
code
func countAndSay(n int) string {
return gen("1",n-1)
}
func gen(str string,n int) string{
if n==0{
return str
}
idx:=0
res:=[]byte{}
for idx<len(str){
c:=str[idx]
l:=idx
for j:=idx;j<len(str);j++{
if str[j]!=c{
break
}
l = j
}
n:=l-idx+1
res = append(res,byte(n)+'0')
res = append(res,c)
idx = l+1
}
return gen(string(res),n-1)
}
Author: hai-na-bai-chuan-11
Link: https://leetcode-cn.com/problems/count-and-say/solution/jian-dan-di-gui-shi-xian-by-hai-na-bai-c-mrq4/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.Complexity analysis
Complexity analysis
Time complexity: O(N) × M) Where N is the given positive integer and M is the maximum length in the generated string.
Space complexity: O(M). Where M is the maximum length in the generated string.