Strings Differ by One Character — LeetCode 1554 Python Solution
MediumLeetCode PremiumHash TableStringHash FunctionRolling Hash
- Problem
- #1554
- Pattern
- Hash Map
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given a list of strings dict where all the strings are of the same length. Return true if there are 2 strings that only differ by 1 character in the same index, otherwise return false.
Example
- Input
- dict = ["abcd","acbd", "aacd"]
- Output
- true
- Explanation
- Strings "abcd" and "aacd" differ only by one character in the index 1.
Python solution
Python
class Solution:
def differByOne(self, dict: List[str]) -> bool:
s = set()
for word in dict:
for i in range(len(word)):
t = word[:i] + "*" + word[i + 1 :]
if t in s:
return True
s.add(t)
return FalseComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1554. Strings Differ by One Character is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
LeetCode 187Repeated DNA SequencesMediumLeetCode 1461Check If a String Contains All Binary Codes of Size KMediumLeetCode 535Encode and Decode TinyURLMediumLeetCode 1948Delete Duplicate Folders in SystemHardLeetCode 2261K Divisible Elements SubarraysMediumLeetCode 3Longest Substring Without Repeating CharactersMedium
Frequently asked questions
- How hard is LeetCode 1554. Strings Differ by One Character?
- LeetCode 1554. Strings Differ by One Character is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1554. Strings Differ by One Character?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1554. Strings Differ by One Character?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1554. Strings Differ by One Character cover?
- LeetCode 1554. Strings Differ by One Character is tagged Hash Table, String, Hash Function and Rolling Hash on LeetCode.
- Is LeetCode 1554. Strings Differ by One Character a premium problem?
- Yes. LeetCode 1554. Strings Differ by One Character is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.