How to Implement strStr() function in C++?

  • 时间:2020-09-27 14:36:16
  • 分类:网络文摘
  • 阅读:86 次

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) —

推荐阅读:
The 24 Game Algorithm using Depth First Search  How to Count the Path Sum from a Binary Tree using Depth First S  How to Multiply Two Matrices in C++?  How to Compute the Number of Equivalent Domino Pairs?  Stay In The Loop: Google Will Make Sure You Never Miss A Mention  5 Ways to Get More Passive Income for your Blog  4 Useful Website Building Tips for the Rookie Blogger  Do You Know How To Keep Your WordPress Site Safe?  Blogger Disgraced After Making Profits Off Of Cancer Scam  5 Incredibly Powerful Ways to Improve Your Blog Writing 
评论列表
添加评论