[Mock] Microsoft 9

shsh·2021년 6월 16일

Mock

목록 보기

62/93

557. Reverse Words in a String III

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

My Answer 1: Accepted (Runtime: 40 ms - 37.20% / Memory Usage: 15.1 MB - 25.85%)

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split()
        
        for i in range(len(words)):
            tmp = list(words[i])
            tmp.reverse()
            words[i] = ''.join(tmp)
        
        return ' '.join(words)

string 을 reverse 할 수 없어서 리스트로 만들고 reverse 후 다시 string 으로

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

My Answer 1: Accepted (Runtime: 32 ms - 64.17% / Memory Usage: 14.1 MB - 91.08%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        
        def func(head):
            if head is None:
                return
            
            # 교환할 두개의 노드가 있을 때만 (예시: 0 - 1 - 2 - 3 - 4)
            if head.next and head.next.next:
                tmp = head.next             # tmp = 1
                head.next = head.next.next  # 0 - 2 - 3 - 4 & 1 로 분리
                tmp2 = head.next.next       # tmp2 = 3
                tmp.next = tmp2             # 0 - 2 - 3 - 4 & 1 - 3
                head.next.next = tmp        # 0 - 2 - 1 - 3 - 4
                
                head = head.next            # head 포인터 이동
                func(head.next)             # 다음 함수 인자로 swap 후의 오른쪽 노드를 넘기기 (1)
        
        # h1 은 head 앞에 dummy 노드 추가
        h1 = ListNode(0, head)
        # h2 는 h1 포인터 역할
        h2 = h1
        
        func(h1)
        
        return h2.next

head 앞에 dummy 노드를 추가한 후
교환할 두개의 노드 (head.next and head.next.next) 가 있을 경우에만 재귀 돌림

Solution 1: Accepted (Runtime: 76 ms - 5.47% / Memory Usage: 14.4 MB - 14.59%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        pre, pre.next = self, head
        while pre.next and pre.next.next:
            a = pre.next
            b = a.next
            pre.next, b.next, a.next = b, a, b.next
            pre = a
        return self.next

pre.next and pre.next.next 가 있으면 while 문 돌리기

pre.next, b.next, a.next = b, a, b.next 로 바로 swap

212. Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

My Answer 1: Accepted (Runtime: 8024 ms - 29.88% / Memory Usage: 14.6 MB - 39.59%)

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        
        # board 알파벳의 종류와 개수 확인
        dic = {}
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] in dic:
                    dic[board[i][j]] += 1
                else:
                    dic[board[i][j]] = 1
        
        # w 에 유효한 word 만 저장
        # 유효 => board 값들로 조합해서 만들 수 있는 단어들
        w = []
        for i in range(len(words)):
            tmp = 1
            for j in range(len(words[i])):
                if words[i][j] not in dic:
                    words[i] = ""
                    tmp = 0
                    break
            if tmp:
                w.append(words[i])
        
        # string 은 모든 단어들 사이에 1 을 넣고 연결한 str
        # ex) ["oath","pea","eat","rain"] => "oath1pea1eat1rain"
        # func 에서 지금 보고 있는 word 가 정답이 될 가능성이 있는지 판단해줌
        string = '1'.join(w)
        
        
        def func(i, j, word):
            # 지금까지의 word 가 유효한지 확인
            if word not in string:
                return
            else:
                # 단어가 완성되면 self.ans 에 추가 & w 에서는 삭제
                if word in w:
                    self.ans.add(word)
                    w.remove(word)
            
            # 인덱스를 벗어나면 return
            if i < 0 or j < 0 or i > len(board)-1 or j > len(board[0])-1:
                return
            
            # 안 가본 사방 둘러보기
            # 위
            if i > 0 and board[i-1][j] != "1":
                tmp = board[i-1][j]
                board[i-1][j] = "1" # 방문했다는 표시
                func(i-1, j, word+tmp)
                board[i-1][j] = tmp # 원상복구
            # 아래
            if i < len(board)-1 and board[i+1][j] != "1":
                tmp = board[i+1][j]
                board[i+1][j] = "1" # 방문했다는 표시
                func(i+1, j, word+tmp)
                board[i+1][j] = tmp # 원상복구
            # 왼쪽
            if j > 0 and board[i][j-1] != "1":
                tmp = board[i][j-1]
                board[i][j-1] = "1" # 방문했다는 표시
                func(i, j-1, word+tmp)
                board[i][j-1] = tmp # 원상복구
            # 오른쪽
            if j < len(board[0])-1 and board[i][j+1] != "1":
                tmp = board[i][j+1]
                board[i][j+1] = "1" # 방문했다는 표시
                func(i, j+1, word+tmp)
                board[i][j+1] = tmp # 원상복구
        
        
        self.ans = set()
        
        # board 값마다 시작값으로 잡고 func 돌리기
        for i in range(len(board)):
            for j in range(len(board[i])):
                tmp = board[i][j]
                board[i][j] = "1"
                func(i, j, tmp)
                board[i][j] = tmp
            # 이미 단어가 다 만들어졌으면 break
            if w is None:
                break
        
        return list(self.ans)