-
[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