709382. Substring
Easy
Substring
Summary
This problem is about finding all occurrences of a given substring within a larger string. The key concept involved is string manipulation, specifically pattern matching.
Detailed Explanation
To solve this problem, we can use the following approach:
- Iterate through the large string and for each position, check if the current character matches the first character of the target substring.
- If it does, then compare the remaining characters in the large string with the target substring. If they match, add the starting index to the result list.
- Continue this process until the end of the large string is reached.
Here's a step-by-step breakdown:
- Initialize an empty list
resultto store the indices of the occurrences. - Iterate through the large string using two pointers:
iandj. - For each position
i, check if the character at that position matches the first character of the target substring. If it does, then:- Compare the remaining characters in the large string (from position
i) with the target substring. If they match, add the starting indexito the result list. - Move both pointers forward by one position to check the next occurrence.
- Compare the remaining characters in the large string (from position
- Continue this process until the end of the large string is reached.
Time complexity: O(n*m), where n is the length of the large string and m is the length of the target substring. This is because we're scanning the large string character by character, and for each match, we're comparing the remaining characters with the target substring. Space complexity: O(1), as we only need a constant amount of space to store the result list.
Here's an ASCII art diagram illustrating the process:
Large String: ...helloworld...
Target Substring: hello
i | j
-----|-----
...h | e (match) => compare remaining characters
...he | l (match) => add index to result, move both pointers forward
...hel | l (no match)
...hell | o (match) => add index to result, move both pointers forward
...
Optimized Solutions
C++
import java.util.ArrayList;
import java.util.List;
public class Main {
public static List<Integer> findSubstrings(String largeString, String targetSubstring) {
List<Integer> result = new ArrayList<>();
int n = largeString.length();
int m = targetSubstring.length();
for (int i = 0; i <= n - m; i++) {
boolean match = true;
for (int j = 0; j < m; j++) {
if (!largeString.substring(i + j, i + j + 1).equals(targetSubstring.substring(j, j + 1))) {
match = false;
break;
}
}
if (match) {
result.add(i);
}
}
return result;
}
public static void main(String[] args) {
String largeString = "helloworld";
String targetSubstring = "hello";
List<Integer> result = findSubstrings(largeString, targetSubstring);
for (int i : result) {
System.out.println("Found substring at index: " + i);
}
}
}