ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [LeetCode] Two Pointer, Sliding Window
    알고리즘 2022. 4. 26. 01:06

    [LeetCode] 557. Reverse Words in a String III

    방법_#1

    time O(N) space O(N)
    스페이스를 기준으로 문자열을 분리한 뒤, 각각의 문자열을 리버스한 뒤 결합

    class Solution(object):
    
        def reverseWord(self, word):
            return word[::-1]
    
    
        def reverseWords(self, s):
            """
            :type s: str
            :rtype: str
            """
            # time :O(N) space: O(N)
    
            arr = s.split()
    
            l = list(map(self.reverseWord, arr))
            r = ""
    
            for k in range(len(l)):
                r += l[k]
                if (k != len(l) - 1):
                    r += " "
            return r

    방법_#2

    투포인터 사용

    class Solution(object):
        def reverseWords(self, s):
            """
            :type s: str
            :rtype: str
            """
            a = 0
            b = 0
    
            r = ""
    
            while (b < len(s)):
                if (s[b] != " "):
                    b += 1
                elif (s[b] == " "):
                    r += s[a:b+1][::-1]
                    b += 1
                    a = b
    
            r += " "
            r += s[a:b+1][::-1]
    
            return r[1:]

    19. Remove Nth Node From End of List

    풀이_#1

    정석풀이

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution(object):
        def removeNthFromEnd(self, head, n):
            """
            :type head: ListNode
            :type n: int
            :rtype: ListNode
            """
            cur = head
            l = 0
            while (cur):
                l += 1
                cur = cur.next
    
            dIdx = l - n
    
            idx =0
            t = head
            b = None
            while (idx < dIdx):
                b = t
                idx += 1
                t = t.next
    
            if (b):
                b.next = t.next
            else:
                head = t.next
    
    
            return head

    풀이_#2

    One pass 로 풀기.

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution(object):
        def removeNthFromEnd(self, head, n):
            """
            :type head: ListNode
            :type n: int
            :rtype: ListNode
            """
            i = 0
            cur = head
            d = None
            s = 0
            flag = False
            before = None
    
            while (cur):
                if (flag):
                    before = d
                    d = d.next
                if (not flag and i + 1 == n):
                    flag = True
                    d = head
    
                i += 1
                cur = cur.next
    
            if (before):
                before.next = d.next
            else:
                head = d.next
            return head

    3. Longest Substring Without Repeating Characters

    분류: sliding Window

    원래는 dictinary 를 활용한 풀이가 있음
    하지만 내가 한 set 풀이는 좀 느린대신 space 가 이득봄.

    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            l = 0
            r = 0
            n = len(s)
            include = set()
            cnt = 0
    
            while (r < n and l <= r):
                if not s[r] in include:
                    include.add(s[r])
                    r += 1
                    cnt = max(cnt, r - l)
                else:
                    include.discard(s[l])
                    l += 1
    
            return cnt

    567. Permutation in String

    방법_#1

    time O(N* K^2 * logK)

    class Solution(object):
    
    
        def checkInclusion(self, s1, s2):
            """
            :type s1: str
            :type s2: str
            :rtype: bool
            """
    
    
            sortS = sorted(s1)
    
            k = len(s1)
            n = len(s2)
    
            if (k > n):
                return False
    
            # O(N-k) * O(K) * O(KlogK) = O(N*K^2*logK) 
            for i in range(n + 1 - k):
                if (sortS == sorted(s2[i:i+k])):
                    return True
    
                else:
                    i += 1
            return False     

    방법_#2

    time O(N* K^2)

    import collections
    
    class Solution(object):
    
    
        def checkInclusion(self, s1, s2):
            """
            :type s1: str
            :type s2: str
            :rtype: bool
            """
    
            d = collections.Counter(s1)
    
            k = len(s1)
            n = len(s2)
    
            if (k > n):
                return False
    
            # O(N-K) * O(K) * O(K) * O(1) (lowercase 로만 이루어져있기때문에)
            for i in range(n + 1 - k):
                d2 = collections.Counter(s2[i:i+k])
                if (d == d2):
                    return True
                else:
                    i += 1
            return False

    방법_#3

    time O(N)

    import collections
    
    class Solution(object):
    
    
        def checkInclusion(self, s1, s2):
            """
            :type s1: str
            :type s2: str
            :rtype: bool
            """
    
            d = collections.Counter(s1)
    
    
            k = len(s1)
            n = len(s2)
    
    
            if (k > n):
                return False
    
            d2 = collections.Counter(s2[:k])
    
            if (d == d2):
                return True
    
            # O(N-K)
            for i in range(n - k):
                if (d2[s2[k+i]] == 0):
                    d2[s2[k+i]] = 1
                else:
                    d2[s2[k+i]] += 1
    
                if (d2[s2[i]] > 1):
                    d2[s2[i]] -= 1
                else:
                    del d2[s2[i]]
    
                if (d == d2):
                    return True
    
                i+= 1
            return False

    '알고리즘' 카테고리의 다른 글

    [LeetCode] BFS 와 접근법  (0) 2022.04.28
    [LeetCode] 이진트리 문제 -Feat: 재귀  (0) 2022.04.27
    [LeetCode] 167. Two Sum II - Input Array Is Sorted  (0) 2022.04.24
    [LeetCode] 283. Move Zeroes  (0) 2022.04.24
    [LeetCode] 189. Rotate Array  (0) 2022.04.24
Designed by Tistory.