[Leetcode]28. Implement strStr()

📄 Description

Implement strStr().

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.

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().

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Constraints:

• 1 <= haystack.length, needle.length <= 104
• haystack and needle consist of only lowercase English characters.

💻 My Submission

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        
        # if needle is empty
        if needle=="": return 0
        _len=len(needle)      
        for i in range(len(haystack)-_len+1):
            # if needle is part of the haystack
            if haystack[i:i+_len]==needle: return i
        # if needle is not part of the haystack  
        return -1

🕐 Complexity

Time Complexity: O(n*h)
The string comparison is O(n) where n is size of needle so solution is O(n*h) at best where h is size of haystack.

❓ How can I improve it?

☝ About slicing strings - deep copy vs shallow copy

When you slice the string like haystack here for example, you're creating a copy of the string.

How to slice a list?

시작인덱스:종료인덱스:step]
종료인덱스의 원소는 포함되지 않고 바로 앞 원소까지만 포함된다.

📌 변수 간 대입 - immutable vs mutable

mutable한 객체의 변수 간 대입

• mutable 객체: list, set, dict
• 예를 들어 list의 얕은 복사의 경우,
  - b 에 a를 할당하면 값이 할당되는 것이 아니라 같은 메모리 주소를 바라본다.
  - 따라서 b를 변경하면 같이 a도 바뀐다.

immutable한 객체의 변수 간 대입

• immutable 객체: bool. int, float, tuple, str, frozenset
• 예를 들어 str의 얕은 복사의 경우,
  - b 에 a를 할당하면 값이 할당되는 것이 아니라 같은 메모리 주소를 바라본다.
  - 하지만 b에 다른 값을 할당하면 재할당이 이루어지며 메모리 주소가 변경된다.
  • 따라서 a와 b는 다른 값을 가진다.
• the value of the object cannot be updated. When assigned, the two variables are the same object, but when one is updated to a new value, it becomes a different object and the other remains the same.

a="hello"
b=a
# a=hello
# b=hello
print(a is b)
> True

# b에 다른 값을 할당하는 경우
b="python"
# a=hello
# b=python
print(a is b)
> False

📌 Deep copy vs Shallow copy

shallow copy(얕은 복사)

1. 슬라이싱(slicing)

• 슬라이싱(slicing)을 통해서 값을 할당하면 새로운 id가 부여되며, 서로 영향을 받지 않는다.

a = [1,2,3]
b = a[:]
print(id(a)) 
# 4396179528
print(id(b))
# 4393788808

위처럼 리스트 a와 리스트 b의 id는 다르다.

>>> a == b
True
>>> a is b
False

따라서 위와 같은 결과가 나온다.

💭 문제: mutable 객체 안에 mutalbe 객체인 경우, 예를 들어 2차원 배열의 경우!

l = [0, 1, [2, 3]]
l_whole_slice = l[:]

• id(l) 과 id(l_whole_slice) 값은 다르지만, 그 내부의 객체 id(l[0]) 과 id(l_whole_slice[0])은 같은 주소를 바라보고 있다.
• 재할당하는 경우 문제가 없지만(메모리 주소도 변경됨), l[1] 값을 변경하면 l_whole_slice[1]도 따라 변경된다.

l[1] = 100
l[2][0] = 200
print(l)
# [0, 100, [200, 3]]

print(l_whole_slice)
# [0, 1, [200, 3]]

2. copy 모듈의 copy() method
3. lists, dictionaries, etc의 copy() method
4. list(), dict(), etc

deep copy(깊은 복사)

• 내부 객체들까지 모두 새롭게 copy 되는 것.
• copy 모듈의 deepcopy() method는 깊은 복사(deep copy)에 해당한다.

l = [0, 1, [2, 3]]
l_deepcopy = copy.deepcopy(l)

print(l is l_deepcopy)
# False

print(l[2] is l_deepcopy[2])
# False

l[1] = 100
l[2][0] = 200
print(l)
# [0, 100, [200, 3]]

print(l_deepcopy)
# [0, 1, [2, 3]]

References

• https://leetcode.com/problems/implement-strstr/discuss/12814/My-answer-by-Python
• https://wikidocs.net/16038
• https://note.nkmk.me/en/python-copy-deepcopy/