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: 2

Example 2:
Input: haystack = “aaaaa”, needle = “bba”
Output: -1

Clarification:
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 
评论列表
添加评论