How to Implement strStr() function in C++?
- 时间:2020-09-27 14:36:16
- 分类:网络文摘
- 阅读:89 次
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1:
Input: haystack = “hello”, needle = “ll”
Output: 2Example 2:
Input: haystack = “aaaaa”, needle = “bba”
Output: -1Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().
strStr() implementation in C++
The implementation should consider the corner cases, when the needle is empty, the result should be always 0. The following implementation of strStr() method in C++ has a time complexity O(MN) where M and N are the lengths of the input haystack and needle string.
The outer loop should be from 0 to the length of M-N+1. And the inner loop checks if the substring of haystack matches the needle. This is not the optimial solution as there will be a KMP algorithm which requires a pre-computation.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public: int strStr(string haystack, string needle) { for (int i = 0; i + needle.size() - 1 < haystack.size(); ++ i) { bool ok = true; for (int j = 0; j < needle.size(); ++ j) { if (haystack[i + j] != needle[j]) { ok = false; break; } } if (ok) return i; } return (needle.size() == 0) ? 0 : -1; } }; |
class Solution { public: int strStr(string haystack, string needle) { for (int i = 0; i + needle.size() - 1 < haystack.size(); ++ i) { bool ok = true; for (int j = 0; j < needle.size(); ++ j) { if (haystack[i + j] != needle[j]) { ok = false; break; } } if (ok) return i; } return (needle.size() == 0) ? 0 : -1; } };
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:Bruteforce/DFS/Backtracking Algorithm using Javascript to Solve DFS and BFS Algorithm to Find Numbers With Same Consecutive Diff How to Remove Items/Entries with Specific Values from Map/HashMa Find the Real Root of 4^x + 6^x = 9^x Depth First Search (Backtracking) Algorithm to Solve a Sudoku Ga Using Bitmasking Algorithm to Compute the Combinations of an Arr Flashing the BIOS of HPZ800 Server to 3.61 Rev.A Algorithm to Sum The Fibonacci Numbers How to Adapt Your Blog to Increasing Zero-Click Searches Understanding Marketing Automation & Its Perks for Your Busi
- 评论列表
-
- 添加评论