The Problem
Two strings are considered close if you can attain one from the other using the following operations:
- Operation 1: Swap any two existing characters.
** For example,
abcde -> aecdb - Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
** For example,
aacabb -> bbcbaa(alla's turn intob's, and allb's turn intoa's)
You can use the operations on either string as many times as necessary.
Given two strings,
word1andword2, returntrueifword1andword2are close, andfalseotherwise.
Example 1:
Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"
Example 2:
Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.
Example 3:
Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"
Example 4:
Input: word1 = "cabbba", word2 = "aabbss"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.
Constraints:
1 <= word1.length, word2.length <= 105-
word1andword2contain only lowercase English letters.
Tests
import pytest
from .Day22_DetermineIfTwoStringsAreClose import Solution
s = Solution()
@pytest.mark.parametrize(
"word1,word2,expected",
[
("abc", "bca", True),
("a", "aa", False),
("cabbba", "abbccc", True),
("cabbba", "aabbss", False),
],
)
def test_close_strings(word1, word2, expected):
assert s.closeStrings(word1, word2) == expected
Solution
def count_chars_map(word: str):
counts = {}
for c in word:
if c in counts:
counts[c] = counts[c] + 1
else:
counts[c] = 1
return counts
class Solution:
def closeStrings(self, word1: str, word2: str) -> bool:
w1l = len(word1)
w2l = len(word2)
if w1l != w2l:
return False
w1_counts = count_chars_map(word1)
w2_counts = count_chars_map(word2)
if sorted(list(w1_counts.keys())) != sorted(list(w2_counts.keys())):
return False
return sorted(list(w1_counts.values())) == sorted(list(w2_counts.values()))
Commentary
This solution was accepted but didn't perform very well. Publishing this now but plan to come back and improve it later.
Top comments (0)