How hard is LeetCode 2452. Words Within Two Edits of Dictionary?

LeetCode 2452. Words Within Two Edits of Dictionary is rated Medium on LeetCode.

What is the time complexity of LeetCode 2452. Words Within Two Edits of Dictionary?

The Python solution on this page runs in O(m \times n \times l), where m and n are the lengths of the arrays \textit{queries} and \textit{dictionary} respectively, and l is the length of the word.

What is the space complexity of LeetCode 2452. Words Within Two Edits of Dictionary?

The Python solution on this page uses O(total characters) auxiliary space.

What topics does LeetCode 2452. Words Within Two Edits of Dictionary cover?

LeetCode 2452. Words Within Two Edits of Dictionary is tagged Trie, Array and String on LeetCode.

Words Within Two Edits of Dictionary — LeetCode 2452 Python Solution

MediumTrieArrayString

Problem: #2452
Pattern: Trie
Reading time: 2 min
Source: leetcode.com

The problem

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

Example

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".

Python solution

Python

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        ans = []
        for s in queries:
            for t in dictionary:
                if sum(a != b for a, b in zip(s, t)) < 3:
                    ans.append(s)
                    break
        return ans

Complexity

Measure	Complexity
Time	O(m \times n \times l), where m and n are the lengths of the arrays \textit{queries} and \textit{dictionary} respectively, and l is the length of the word
Space	O(total characters) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 2452. Words Within Two Edits of Dictionary is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Trie.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2452. Words Within Two Edits of Dictionary?: LeetCode 2452. Words Within Two Edits of Dictionary is rated Medium on LeetCode.
What is the time complexity of LeetCode 2452. Words Within Two Edits of Dictionary?: The Python solution on this page runs in O(m \times n \times l), where m and n are the lengths of the arrays \textit{queries} and \textit{dictionary} respectively, and l is the length of the word.
What is the space complexity of LeetCode 2452. Words Within Two Edits of Dictionary?: The Python solution on this page uses O(total characters) auxiliary space.
What topics does LeetCode 2452. Words Within Two Edits of Dictionary cover?: LeetCode 2452. Words Within Two Edits of Dictionary is tagged Trie, Array and String on LeetCode.