0858EasyString

Matching Two Four Letter Dials

Tracked in this browser only

Trains the technique from

LeetCode 2839Check if Strings Can be Made Equal With Operations I

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two dials each show exactly four lowercase letters, given as s1 and s2.

One turn on a dial picks two of its positions that are two apart and swaps the letters in them. So on a dial reading positions 0, 1, 2, 3, a turn swaps positions 0 and 2, or swaps positions 1 and 3. Either dial may be turned, any number of times.

Return true when the two dials can be made to read the same, and false otherwise.

Examples

Example 1

Input: s1 = "abcd", s2 = "cdab"
Output: true

Turning the first dial at positions 0 and 2 gives "cbad", and turning it again at positions 1 and 3 gives "cdab".

Example 2

Input: s1 = "abcd", s2 = "abdc"
Output: false

Positions 2 and 3 hold different letters on the two dials, and no turn can move a letter from an even position to an odd one.

Example 3

Input: s1 = "abab", s2 = "baba"
Output: false

Both pairs hold the same two letters on each dial, so the turns can bring the readings together.

Constraints

s1.length == 4
s2.length == 4
s1 and s2 consist of lowercase English letters only

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def dials_can_match(s1: str, s2: str) -> bool:

Java

public boolean dialsCanMatch(String s1, String s2)

The intended approach

Time O(1): the dials are a fixed four letters long.Space O(1).

A turn only ever exchanges two positions that are two apart, so a letter can never move between the even positions and the odd ones. That splits each dial into two independent pairs: positions 0 and 2, and positions 1 and 3. Within a pair the letters can be put in either order and nothing else changes, so the dials can be matched exactly when each pair holds the same two letters, which is a comparison of the two letters as an unordered pair.

Pythonentry point: dials_can_match

def dials_can_match(s1, s2):
    return (sorted([s1[0], s1[2]]) == sorted([s2[0], s2[2]])
            and sorted([s1[1], s1[3]]) == sorted([s2[1], s2[3]]))

The obvious version

Explore every dial reading reachable from the first by repeated turns, keeping a set of what has been seen, and check whether the second dial's reading turns up. Makes no argument about positions splitting into two groups.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_dials_can_match(s1, s2):
    seen = {s1}
    frontier = [s1]
    while frontier:
        nxt = []
        for cur in frontier:
            for a, b in ((0, 2), (1, 3)):
                chars = list(cur)
                chars[a], chars[b] = chars[b], chars[a]
                cand = "".join(chars)
                if cand not in seen:
                    seen.add(cand)
                    nxt.append(cand)
        frontier = nxt
    other = {s2}
    frontier = [s2]
    while frontier:
        nxt = []
        for cur in frontier:
            for a, b in ((0, 2), (1, 3)):
                chars = list(cur)
                chars[a], chars[b] = chars[b], chars[a]
                cand = "".join(chars)
                if cand not in other:
                    other.add(cand)
                    nxt.append(cand)
        frontier = nxt
    return len(seen & other) > 0

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in