Re: [閒聊] 每日LeetCode

[yam276 (史萊哲林的優等生)]

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-
string/


28. Find the Index of the First Occurrence in a String

Given two strings needle and haystack, return the index of the first
occurrence of needle in haystack, or -1 if needle is not part of haystack.

在較長的A字串裡面找B字串


Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0


Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1


Step:

0. 檢查B字串empty

1. 從A字串開始跑

1-1. 檢查是否符合B字串，否則break，從下個char重複1-1

1-2. 如果檢查到跟B一樣的字串(j == needle_size)，

     return檢查起點(i of haystack_size)

2. 重複1都沒有成功，return -1


Code:

impl Solution
{
    pub fn str_str(haystack: String, needle: String) -> i32
    {
        if needle.is_empty()
        {
            return 0;
        }

        let haystack_size = haystack.len();
        let needle_size = needle.len();

        for i in 0..haystack_size
        {
            let mut j = 0;
            while j < needle_size
            {
                if haystack.chars().nth(i + j) != needle.chars().nth(j)
                {
                    break;
                }

                j += 1;
            }

            if j == needle_size
            {
                return i as i32;
            }
        }

        return -1;
    }
}


C++:

class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        if (needle.empty())
            return 0;

        int haystack_size = haystack.size();
        int needle_size = needle.size();

        for (int i = 0; i <= haystack_size - needle_size; i++)
        {
            int j;
            for (j = 0; j < needle_size; j++)
            {
                if (haystack[i + j] != needle[j])
                    break;
            }

            if (j == needle_size)
                return i;
        }

        return -1;
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689758147.A.9DB.html