[LeetCode] Two Pointer, Sliding Window

[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