saurus2
Saurus2
saurus2
전체 방문자
오늘
어제
  • 분류 전체보기
    • 개발
      • AJAX
    • ML Ops
    • Profile
    • 음식점
    • 배낭여행
    • 컴퓨터공학
      • 알고리즘 공부
      • C++
      • Sever 스터디
      • Java spring
      • 알고리즘 _ 문제해결
      • 딥러닝
      • Java 정리
      • Python
      • LeetCode 1000
      • Machine Learning Study
      • Sign language Detection Pro..
      • LeetCode Solutions
    • 비콘
    • 데일리 리포트
    • 유학일기
      • 영어 공부
      • Daily
    • AI Master Degree
      • Data Mining
      • AI and Data engineering
      • Math Foundations for Decisi..
      • Natural Language Processing

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

인기 글

태그

  • DFS
  • 알고리즘문제해결
  • two pointer
  • LeetCode
  • BFS
  • 개발자 취업준비
  • 알고리즘
  • 취준
  • 온라인저지
  • 백준
  • c++
  • 파이썬
  • 개발자
  • 문제해결능력
  • 리트코드
  • 릿코드
  • Python
  • 딥러닝
  • 딕셔너리
  • 취업준비

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
saurus2

Saurus2

컴퓨터공학/LeetCode 1000

[LeetCode] 1662. Check If Two String Arrays are Equivalent

2022. 10. 26. 03:12

1662. Check If Two String Arrays are Equivalent

Easy

Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.

A string is represented by an array if the array elements concatenated in order forms the string.

 

Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

 

Constraints:

  • 1 <= word1.length, word2.length <= 103
  • 1 <= word1[i].length, word2[i].length <= 103
  • 1 <= sum(word1[i].length), sum(word2[i].length) <= 103
  • word1[i] and word2[i] consist of lowercase letters.

문제 풀이

두개의 리스트에 하나 이상의 단어들이 저장되어 있다.

이 단어들을 합쳐서 비교했을때 두 단어가 같으면 True 아니면 False 을 리턴해라.

제한 사항을 보면 단어 리스트의 길이가 10^3이 되는 것을 볼 수 있다. 

브루트 포스로 푸는것이 가능해보인다. 

글자 붙여서 비교

  • 각 리스트의 단어들을 string으로 모두 합치고 비교하여 답을 리턴한다.

투포인터

  • 다시 말하자면, 포인터를 4개를 만든다.
  • 각각 리스트의 인덱스, 그 리스트 안의 단어의 인덱스라고 생각하면 된다. 
  • 만약 리스트에 단어의 길이와 그 리스트 안의 단어 인덱스를 가르키는 포인터가 같아지면,
  • 리스트 인덱스 포인터를 1 증가시키고, 단어 인덱스 포인터를 0으로 만들어준다. 
  • 단어 인덱스 포인터들은 계속해서 1씩 증가시키고, 리스트 인덱스 포인터가 전체 리스트 길이가 넘지않을때 까지 반복하면서 각 단어가 같은지 비교하여 답을 출력한다.

소스 코드

글자 붙여서 비교

  • Time Complexity: O(N * K) [word1 길이 * word2 길이]
  • Space Complexity: O(N * K)
class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        # merge every word in each list
        temp1, temp2 = '', ''
        for word in word1:
            temp1 += word
        for word in word2:
            temp2 += word
        if temp1 == temp2:
            return True
        return False

투포인터

  • Time complexity: O(N * K)
  • Space Complexity: O(1) 
class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        # Two Pointer
        p1, p2 = 0, 0
        str_p1, str_p2 = 0, 0
        while p1 < len(word1) and p2 < len(word2):
            if word1[p1][str_p1] != word2[p2][str_p2]:
                return False
            str_p1 += 1
            str_p2 += 1
            if str_p1 == len(word1[p1]):
                p1 += 1
                str_p1 = 0
            if str_p2 == len(word2[p2]):
                p2 += 1
                str_p2 = 0
        return p1 == len(word1) and p2 == len(word2)
저작자표시 (새창열림)

'컴퓨터공학 > LeetCode 1000' 카테고리의 다른 글

[LeetCode] 49. Group Anagrams  (0) 2022.10.29
[LeetCode] 22. Generate Parentheses  (0) 2022.10.26
[LeetCode - Online Assessment 기출] Stars and Bars* / 2055. Plates Between Candles  (0) 2022.10.21
[LeetCode - Online Assessment 기출] Circular Printer  (0) 2022.10.21
[LeetCode - Didi labs 기출문제] 265. Paint House II  (0) 2022.10.20
    '컴퓨터공학/LeetCode 1000' 카테고리의 다른 글
    • [LeetCode] 49. Group Anagrams
    • [LeetCode] 22. Generate Parentheses
    • [LeetCode - Online Assessment 기출] Stars and Bars* / 2055. Plates Between Candles
    • [LeetCode - Online Assessment 기출] Circular Printer
    saurus2
    saurus2
    Simple is Best

    티스토리툴바