Implement strStr() ใน Python

สมมติว่าเรามีสตริงสองตัวคือ str และ sub_str เราต้องหาการเกิดครั้งแรกของ sub_str ใน str เช่นถ้าสตริง str คือ "helloworld" และ substring คือ "lo" ผลลัพธ์จะเป็น 3

สิ่งนี้สามารถทำได้ด้วยฟังก์ชัน strstr() ใน C เราต้องออกแบบฟังก์ชันอีกตัวที่คล้ายกับ strstr() ใน C

วิธีการแก้ปัญหา

• i := 0, j := 0, m := ความยาวของ sub_str และ n := ความยาวของ str
• ถ้า m = 0 ให้คืนค่า 0
• while i < n และ n - i + 1 >= m:
  • ถ้า str[i] = sub_str[j]:
    • temp := j
    • while j < m และ i < n และ sub_str[j] == str[j]:
      • เพิ่ม i และ j ขึ้น 1
    • ถ้า j = m ให้คืนค่า temp
    • i := temp + 1
    • j := 0
  • มิฉะนั้น เพิ่ม i ขึ้น 1
• คืนค่า -1

ตัวอย่าง (Python)

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        i = 0
        j = 0
        m = len(needle)
        n = len(haystack)
        if m == 0:
            return 0
        while i < n and n - i + 1 >= m:
            if haystack[i] == needle[j]:
                temp = i
                while j < m and i < n and needle[j] == haystack[i]:
                    i += 1
                    j += 1
                if j == m:
                    return temp
                i = temp + 1
                j = 0
            else:
                i += 1
        return -1

haystack = "helloworld"
needle = "lo"
ob1 = Solution()
print(ob1.strStr(haystack, needle))

อินพุต

haystack = "helloworld" needle = "lo"

เอาต์พุต

3