Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
📢 preface
| 🚀 Algorithm 🚀 |
- 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
- 🌲 tip: the programming languages used in this column are C# and Java
- 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
- 🌲 today is the force button algorithm continued to punch the card for the 15th day 🎈!
| 🚀 Algorithm 🚀 |
🌲 Example of original problem
Implement the strStr() function.
Given two strings haystack and needle, find the first place in the haystack string where needle appears (the subscript starts at 0).
If none exists, -1 is returned.
Description:
What value should we return when needle is an empty string? This is a good question to ask in an interview.
For this case, we should return 0 when needle is an empty string. This is consistent with the C language STRSTR () and the Java definition of indexOf().
The sample1: Enter: haystack ="hello", needle = "ll"Output:2
Copy the codeThe sample2: Enter: haystack ="aaaaa", needle = "bba"Output:- 1
Copy the codeThe sample3: Enter: haystack ="", needle = ""Output:0
Copy the codeTip:
- 0 <= haystack.length, needle.length <= 5 * 104
- Haystack and needle are only lowercase characters
🌻C# method 1: violence method
Thinking analytical
My first thought was that using IndexOf would return the first index directly
But there is no algorithm to speak of haha, after the code is also pasted ~
The brute force method uses a double-layer for loop to match the string needle with all m substrings of the string haystack once.
To reduce unnecessary matches, each time a match fails, we immediately stop matching the current substring and continue matching the next substring.
If the current substring matches, we simply return the start of the current substring. −1 is returned if all substrings fail to match.
Code:
public int strStr(string haystack, string needle)
{
int n = haystack.Length, m = needle.Length;
for (int i = 0; i + m <= n; i++)
{
bool flag = true;
for (int j = 0; j < m; j++)
{
if (haystack.Substring(i + j,1) != needle.Substring(j,1))
{
flag = false;
break; }}if (flag)
{
returni; }}return - 1;
}
Copy the codeThe execution result
By execution time:1373Ms, in all C# beat 13.13% of users in submissionMemory consumption:38.2MB, in all CBeat 61.91% of users in # submissions
Copy the codeComplexity analysis
Time complexity: O(n * m) Space complexity: O(1)
Copy the code🌻C# method two: fool solution
This method uses C# IndexOf to retrieve the index directly, which does not reflect the essence of the algorithm.
Code:
public class Solution {
public int RemoveElement(int[] nums, int val) {
if(nums.Length == 0) return 0;
int count = 0;
for(int i = 0; i < nums.Length; i++)
if(nums[i] ! = val) nums[count++] = nums[i];returncount; }}Copy the codeThe execution result
By execution time:920Ms, in all CBeat 30.06% of users in # submissionsMemory consumption:24.3MB, in all CBeat 13.88% of users in # submissions
Copy the code🌻Java method 1: Brute force method
This approach is consistent with the first C# solution
Code:
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
for (int i = 0; i + m <= n; i++) {
boolean flag = true;
for (int j = 0; j < m; j++) {
if(haystack.charAt(i + j) ! = needle.charAt(j)) { flag =false;
break; }}if (flag) {
returni; }}return -1; }}Copy the codeThe execution result
By execution time:1373Ms, beat out all Java commits13.03% user memory consumption:38.2MB, beat out all Java commits61.91% of the userCopy the codeComplexity analysis
Time complexity: O(n*m) Space complexity: O(1)
Copy the code🌻Java Method 2: KMP solution
Thinking analytical
Let’s just say I don’t understand. Buckle big guy reference from the force come over!
Code:
class Solution {
/ / KMP algorithm
// ss: original string pp: matching string
public int strStr(String ss, String pp) {
if (pp.isEmpty()) return 0;
// Read the length of the original and matching strings respectively
int n = ss.length(), m = pp.length();
// Both the original string and the matching string are preceded by a space so that their subscripts start at 1
ss = "" + ss;
pp = "" + pp;
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
// Construct the next array with the length of the matching string (next array is related to matching string)
int[] next = new int[m + 1];
// I = 2, j = 0, I < or equal to the length of the matching string
for (int i = 2, j = 0; i <= m; i++) {
// next(j) = next(j)
while (j > 0&& p[i] ! = p[j +1]) j = next[j];
// if the match is successful, make j++ first
if (p[i] == p[j + 1]) j++;
// Update next[I] to end the loop, I ++
next[i] = j;
}
I = 1, j = 0, I is less than or equal to the length of the original string.
for (int i = 1, j = 0; i <= n; i++) {
J = next(j)
while (j > 0&& s[i] ! = p[j +1]) j = next[j];
// if the match is successful, j++ is used first, and i++ is used after the loop is completed
if (s[i] == p[j + 1]) j++;
// If the whole section matches, return the index directly
if (j == m) return i - m;
}
return -1; }} Link: HTTPS://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/
Copy the codeThe execution result
By execution time:3Ms, beat out all Java commits72.84% user memory consumption:38.5MB, beat out all Java commits29.32% of the userCopy the codeComplexity analysis
Time complexity: O(m+n) Space complexity: O(m)Copy the code💬 summary
- Today is the 15th day of buckle algorithm clocking!
- The article USES the
C#andJavaTwo programming languages to solve the problem - Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
- That’s the end of today’s algorithm sharing, see you tomorrow!
