从零开始算法之路 ---- 实现 strStr()

深藏阁楼爱情的钟 2021-10-15 14:51 370阅读 0赞

**前言**:小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）  
**题源:** 力扣(LeetCode）[https://leetcode-cn.com/problems/implement-strstr][https_leetcode-cn.com_problems_implement-strstr]  
**题目描述:**  
实现 strStr() 函数。  
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

**示例 1:**  
  输入: haystack = “hello”, needle = “ll”  
  输出: 2

**示例 2:**  
  输入: haystack = “aaaaa”, needle = “bba”  
  输出: -1

#### 解决方案一 ####

##### 思路： #####

**特殊情况：**(1) 当 needle是空字符串时我们应当返回 0 (2) 当 haystack 字符串大小大于 needle 字符串大小，返回 -1  
**普遍情况:** 在 haystack 中 寻找 needle，定义一个 needle 指针 j, 如果两个字符中的字符相等 j 加 1， 当 j 等于 needle 字符串的大小返回起始位置。如果中途出现不相等从上一次开始相等位置的下一个位置继续寻找。详情看代码。  
**代码：**

class Solution { 
    public:
        int strStr(string haystack, string needle) { 
            // 代码中多处用到 needle.size()，在这里定义一个变量存下来，减少调用函数调用次数，提高效率 
    		int needleSize = needle.size();
    			// needle 指针 
        	int j = 0;
    		int i; 
        	// 当 needle是空字符串时我们应当返回 0
        	if( needleSize == 0)
        		return 0;
        	// 当 haystack 字符串大小大于 needle 字符串大小，返回 -1 
        	if(haystack.size() <  needleSize)
        		return -1;	    					
    		for(i = 0; i < haystack.size(); i++){ 
    			// needle 在 haystack 字符中部情况，如果相等返回 needle 起始位置 
    			if(j ==  needleSize)
    			// 相减即 needle 起始位置 
    				return  i -  needleSize;
    			// 如果字符相等
    			if(haystack[i] == needle[j]){ 
    				j++;
    			}else{ 
    				// i 回到两个字符串中字符串上一次开始相等的位置
    				// 这个循环完了 i++ 之后等于 i 到了两个字符串中字符串上一次开始相等位置的下一个位置，重新开始寻找 
    				i = i - j;
    				j = 0; 
    			} 
    		}
    		// 应对 needle 在 haystack 字符尾部的情况
        	if(j ==  needleSize)
    		// 相减即 needle 起始位置 
    			return  i -  needleSize;  
    		return -1;
        }
    };

#### 解决方案二（作弊解法，利用 C++ 库函数） ####

##### 代码： #####

class Solution { 
    public:
        int strStr(string haystack, string needle) { 
            return haystack.find(needle);
            
        }
    };

#### 解决方案三（作弊解法，利用 java String 的函数） ####

##### 代码： #####

class Solution { 
        public int strStr(String haystack, String needle) { 
            return haystack.indexOf(needle);
        }
    }

[https_leetcode-cn.com_problems_implement-strstr]: https://leetcode-cn.com/problems/implement-strstr