[LeetCode - Biweekly Contest 90] 2452. Words Within Two Edits of Dictionary

2452. Words Within Two Edits of Dictionary

Medium

You are given two string arrays, queries and dictionary. All words in each array comprise of lowercase English letters and have the same length.

In one edit you can take a word from queries, and change any letter in it to any other letter. Find all words from queries that, after a maximum of two edits, equal some word from dictionary.

Return a list of all words from queries, that match with some word from dictionary after a maximum of two edits. Return the words in the same order they appear in queries.

 

Example 1:

Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output: ["word","note","wood"]
Explanation:
- Changing the 'r' in "word" to 'o' allows it to equal the dictionary word "wood".
- Changing the 'n' to 'j' and the 't' to 'k' in "note" changes it to "joke".
- It would take more than 2 edits for "ants" to equal a dictionary word.
- "wood" can remain unchanged (0 edits) and match the corresponding dictionary word.
Thus, we return ["word","note","wood"].

Example 2:

Input: queries = ["yes"], dictionary = ["not"]
Output: []
Explanation:
Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.

 

Constraints:

• 1 <= queries.length, dictionary.length <= 100
• n == queries[i].length == dictionary[j].length
• 1 <= n <= 100
• All queries[i] and dictionary[j] are composed of lowercase English letters.

---

문제 풀이 

• 쿼리들과 사전이 주어진다. 
• 쿼리들에 들어있는 단어가 사전안에 있는 단어와 비교해봤을때, 
• 최대 2자리 알파벳을 바꿔서 똑같게 만들 수 있는 쿼리 단어를 구하자.
• 예를 들어, 쿼리의 word는 사전의 wood와 비교했을때 'r'을 'o'로 변경하면 똑같이 맞출 수 있다.
• 제한 사항을 보면 단어들의 총 갯수의 최대가 100이기 때문에 Brute Force를 사용해도 상관 없다.
• 쿼리의 단어를 사전에 단어 모두와 하나씩 비교한다. 
• 그리고 만약 단어의 알파벳이 다른 갯수가 2개를 넘어간다면 정답으로 넣어주고
• 사전을 검색하는 for 루프를 종료해준다. 
• 한번이라도 사전에서 정답을 찾는다면 사전의 다음단어들은 찾을 필요가 없어서 flag로 처리해준다.

소스 코드

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        ans = []
        for word in queries:
            f = False
            for word2 in dictionary:
                if f == False:
                    cnt = 0
                    for l1, l2 in zip(word, word2):
                        if l1 != l2:
                            cnt += 1
                        if cnt > 2:
                            break
                    if cnt <= 2:
                        ans.append(word)
                        f = True
        return ans