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

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)