{"id":4138,"date":"2018-10-02T12:41:33","date_gmt":"2018-10-02T19:41:33","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4138"},"modified":"2018-10-02T12:47:30","modified_gmt":"2018-10-02T19:47:30","slug":"leetcode-28-implement-strstr","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-28-implement-strstr\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 28. Implement strStr()"},"content":{"rendered":"<h1><strong>Problem<\/strong><\/h1>\n<p>Implement\u00a0<a href=\"http:\/\/www.cplusplus.com\/reference\/cstring\/strstr\/\" target=\"_blank\" rel=\"noopener\">strStr()<\/a>.<\/p>\n<p>Return the index of the first occurrence of needle in haystack, or\u00a0<strong>-1<\/strong>\u00a0if needle is not part of haystack.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input:<\/strong> haystack = \"hello\", needle = \"ll\"\r\n<strong>Output:<\/strong> 2\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input:<\/strong> haystack = \"aaaaa\", needle = \"bba\"\r\n<strong>Output:<\/strong> -1\r\n<\/pre>\n<p><strong>Clarification:<\/strong><\/p>\n<p>What should we return when\u00a0<code>needle<\/code>\u00a0is an empty string? This is a great question to ask during an interview.<\/p>\n<p>For the purpose of this problem, we will return 0 when\u00a0<code>needle<\/code>\u00a0is an empty string. This is consistent to C&#8217;s\u00a0<a href=\"http:\/\/www.cplusplus.com\/reference\/cstring\/strstr\/\" target=\"_blank\" rel=\"noopener\">strstr()<\/a>\u00a0and Java&#8217;s\u00a0<a href=\"https:\/\/docs.oracle.com\/javase\/7\/docs\/api\/java\/lang\/String.html#indexOf(java.lang.String)\" target=\"_blank\" rel=\"noopener\">indexOf()<\/a>.<\/p>\n<h1><strong>Solution 1: Brute Force<\/strong><\/h1>\n<p>Time complexity: O(mn)<\/p>\n<p>Space complexity: O(1)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua, 4 ms\r\nclass Solution {\r\npublic:\r\n  int strStr(string haystack, string needle) {\r\n    const int l1 = haystack.length();\r\n    const int l2 = needle.length();\r\n    for (int i = 0; i &lt;= l1 - l2; ++i) {\r\n      int j = 0;\r\n      while (j &lt; l2 &amp;&amp; haystack[i + j] == needle[j]) ++j;\r\n      if (j == l2) return i;\r\n    }\r\n    return -1;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true  \"># Author: Huahua\r\nclass Solution:\r\n  def strStr(self, haystack, needle):\r\n    l1 = len(haystack)\r\n    l2 = len(needle)\r\n    for i in range(l1 - l2 + 1):\r\n      if haystack[i:i+l2] == needle: return i\r\n    return -1<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem Implement\u00a0strStr(). Return the index of the first occurrence of needle in haystack, or\u00a0-1\u00a0if needle is not part of haystack. Example 1: Input: haystack =&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[222,4,314],"class_list":["post-4138","post","type-post","status-publish","format-standard","hentry","category-string","tag-easy","tag-string","tag-substring","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4138","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4138"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4138\/revisions"}],"predecessor-version":[{"id":4143,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4138\/revisions\/4143"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4138"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4138"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4138"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}