Breadth-First Search
String
Description
Strings s1
and s2
are k
-similar (for some non-negative integer k
) if we can swap the positions of two letters in s1
exactly k
times so that the resulting string equals s2
.
Given two anagrams s1
and s2
, return the smallest k
for which s1
and s2
are k
-similar .
Example 1:
Input: s1 = "ab", s2 = "ba"
Output: 1
Explanation: The two string are 1-similar because we can use one swap to change s1 to s2: "ab" --> "ba".
Example 2:
Input: s1 = "abc", s2 = "bca"
Output: 2
Explanation: The two strings are 2-similar because we can use two swaps to change s1 to s2: "abc" --> "bac" --> "bca".
Constraints:
1 <= s1.length <= 20
s2.length == s1.length
s1
and s2
contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}
.
s2
is an anagram of s1
.
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution :
def kSimilarity ( self , s1 : str , s2 : str ) -> int :
def next ( s ):
i = 0
while s [ i ] == s2 [ i ]:
i += 1
res = []
for j in range ( i + 1 , n ):
if s [ j ] == s2 [ i ] and s [ j ] != s2 [ j ]:
res . append ( s2 [: i + 1 ] + s [ i + 1 : j ] + s [ i ] + s [ j + 1 :])
return res
q = deque ([ s1 ])
vis = { s1 }
ans , n = 0 , len ( s1 )
while 1 :
for _ in range ( len ( q )):
s = q . popleft ()
if s == s2 :
return ans
for nxt in next ( s ):
if nxt not in vis :
vis . add ( nxt )
q . append ( nxt )
ans += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 class Solution {
public int kSimilarity ( String s1 , String s2 ) {
Deque < String > q = new ArrayDeque <> ();
Set < String > vis = new HashSet <> ();
q . offer ( s1 );
vis . add ( s1 );
int ans = 0 ;
while ( true ) {
for ( int i = q . size (); i > 0 ; -- i ) {
String s = q . pollFirst ();
if ( s . equals ( s2 )) {
return ans ;
}
for ( String nxt : next ( s , s2 )) {
if ( ! vis . contains ( nxt )) {
vis . add ( nxt );
q . offer ( nxt );
}
}
}
++ ans ;
}
}
private List < String > next ( String s , String s2 ) {
int i = 0 , n = s . length ();
char [] cs = s . toCharArray ();
for (; cs [ i ] == s2 . charAt ( i ); ++ i ) {
}
List < String > res = new ArrayList <> ();
for ( int j = i + 1 ; j < n ; ++ j ) {
if ( cs [ j ] == s2 . charAt ( i ) && cs [ j ] != s2 . charAt ( j )) {
swap ( cs , i , j );
res . add ( new String ( cs ));
swap ( cs , i , j );
}
}
return res ;
}
private void swap ( char [] cs , int i , int j ) {
char t = cs [ i ] ;
cs [ i ] = cs [ j ] ;
cs [ j ] = t ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 class Solution {
public :
int kSimilarity ( string s1 , string s2 ) {
queue < string > q {{ s1 }};
unordered_set < string > vis {{ s1 }};
int ans = 0 ;
while ( 1 ) {
for ( int i = q . size (); i ; -- i ) {
auto s = q . front ();
q . pop ();
if ( s == s2 ) {
return ans ;
}
for ( auto & nxt : next ( s , s2 )) {
if ( ! vis . count ( nxt )) {
vis . insert ( nxt );
q . push ( nxt );
}
}
}
++ ans ;
}
}
vector < string > next ( string & s , string & s2 ) {
int i = 0 , n = s . size ();
for (; s [ i ] == s2 [ i ]; ++ i ) {}
vector < string > res ;
for ( int j = i + 1 ; j < n ; ++ j ) {
if ( s [ j ] == s2 [ i ] && s [ j ] != s2 [ j ]) {
swap ( s [ i ], s [ j ]);
res . push_back ( s );
swap ( s [ i ], s [ j ]);
}
}
return res ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 func kSimilarity ( s1 string , s2 string ) int {
next := func ( s string ) [] string {
i := 0
res := [] string {}
for ; s [ i ] == s2 [ i ]; i ++ {
}
for j := i + 1 ; j < len ( s1 ); j ++ {
if s [ j ] == s2 [ i ] && s [ j ] != s2 [ j ] {
res = append ( res , s [: i ] + string ( s [ j ]) + s [ i + 1 : j ] + string ( s [ i ]) + s [ j + 1 :])
}
}
return res
}
q := [] string { s1 }
vis := map [ string ] bool { s1 : true }
ans := 0
for {
for i := len ( q ); i > 0 ; i -- {
s := q [ 0 ]
q = q [ 1 :]
if s == s2 {
return ans
}
for _ , nxt := range next ( s ) {
if ! vis [ nxt ] {
vis [ nxt ] = true
q = append ( q , nxt )
}
}
}
ans ++
}
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 class Solution :
def kSimilarity ( self , s1 : str , s2 : str ) -> int :
def f ( s ):
cnt = sum ( c != s2 [ i ] for i , c in enumerate ( s ))
return ( cnt + 1 ) >> 1
def next ( s ):
i = 0
while s [ i ] == s2 [ i ]:
i += 1
res = []
for j in range ( i + 1 , n ):
if s [ j ] == s2 [ i ] and s [ j ] != s2 [ j ]:
res . append ( s2 [: i + 1 ] + s [ i + 1 : j ] + s [ i ] + s [ j + 1 :])
return res
q = [( f ( s1 ), s1 )]
dist = { s1 : 0 }
n = len ( s1 )
while 1 :
_ , s = heappop ( q )
if s == s2 :
return dist [ s ]
for nxt in next ( s ):
if nxt not in dist or dist [ nxt ] > dist [ s ] + 1 :
dist [ nxt ] = dist [ s ] + 1
heappush ( q , ( dist [ nxt ] + f ( nxt ), nxt ))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 class Solution {
public int kSimilarity ( String s1 , String s2 ) {
PriorityQueue < Pair < Integer , String >> q
= new PriorityQueue <> ( Comparator . comparingInt ( Pair :: getKey ));
q . offer ( new Pair <> ( f ( s1 , s2 ), s1 ));
Map < String , Integer > dist = new HashMap <> ();
dist . put ( s1 , 0 );
while ( true ) {
String s = q . poll (). getValue ();
if ( s . equals ( s2 )) {
return dist . get ( s );
}
for ( String nxt : next ( s , s2 )) {
if ( ! dist . containsKey ( nxt ) || dist . get ( nxt ) > dist . get ( s ) + 1 ) {
dist . put ( nxt , dist . get ( s ) + 1 );
q . offer ( new Pair <> ( dist . get ( nxt ) + f ( nxt , s2 ), nxt ));
}
}
}
}
private int f ( String s , String s2 ) {
int cnt = 0 ;
for ( int i = 0 ; i < s . length (); ++ i ) {
if ( s . charAt ( i ) != s2 . charAt ( i )) {
++ cnt ;
}
}
return ( cnt + 1 ) >> 1 ;
}
private List < String > next ( String s , String s2 ) {
int i = 0 , n = s . length ();
char [] cs = s . toCharArray ();
for (; cs [ i ] == s2 . charAt ( i ); ++ i ) {
}
List < String > res = new ArrayList <> ();
for ( int j = i + 1 ; j < n ; ++ j ) {
if ( cs [ j ] == s2 . charAt ( i ) && cs [ j ] != s2 . charAt ( j )) {
swap ( cs , i , j );
res . add ( new String ( cs ));
swap ( cs , i , j );
}
}
return res ;
}
private void swap ( char [] cs , int i , int j ) {
char t = cs [ i ] ;
cs [ i ] = cs [ j ] ;
cs [ j ] = t ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 using pis = pair < int , string > ;
class Solution {
public :
int kSimilarity ( string s1 , string s2 ) {
priority_queue < pis , vector < pis > , greater < pis >> q ;
q . push ({ f ( s1 , s2 ), s1 });
unordered_map < string , int > dist ;
dist [ s1 ] = 0 ;
while ( 1 ) {
auto [ _ , s ] = q . top ();
q . pop ();
if ( s == s2 ) {
return dist [ s ];
}
for ( auto & nxt : next ( s , s2 )) {
if ( ! dist . count ( nxt ) || dist [ nxt ] > dist [ s ] + 1 ) {
dist [ nxt ] = dist [ s ] + 1 ;
q . push ({ dist [ nxt ] + f ( nxt , s2 ), nxt });
}
}
}
}
int f ( string & s , string & s2 ) {
int cnt = 0 ;
for ( int i = 0 ; i < s . size (); ++ i ) {
cnt += s [ i ] != s2 [ i ];
}
return ( cnt + 1 ) >> 1 ;
}
vector < string > next ( string & s , string & s2 ) {
int i = 0 , n = s . size ();
for (; s [ i ] == s2 [ i ]; ++ i ) {}
vector < string > res ;
for ( int j = i + 1 ; j < n ; ++ j ) {
if ( s [ j ] == s2 [ i ] && s [ j ] != s2 [ j ]) {
swap ( s [ i ], s [ j ]);
res . push_back ( s );
swap ( s [ i ], s [ j ]);
}
}
return res ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 func kSimilarity ( s1 string , s2 string ) int {
next := func ( s string ) [] string {
i := 0
res := [] string {}
for ; s [ i ] == s2 [ i ]; i ++ {
}
for j := i + 1 ; j < len ( s1 ); j ++ {
if s [ j ] == s2 [ i ] && s [ j ] != s2 [ j ] {
res = append ( res , s [: i ] + string ( s [ j ]) + s [ i + 1 : j ] + string ( s [ i ]) + s [ j + 1 :])
}
}
return res
}
f := func ( s string ) int {
cnt := 0
for i := range s {
if s [ i ] != s2 [ i ] {
cnt ++
}
}
return ( cnt + 1 ) >> 1
}
q := hp { pair { f ( s1 ), s1 }}
dist := map [ string ] int { s1 : 0 }
for {
s := heap . Pop ( & q ).( pair ). s
if s == s2 {
return dist [ s ]
}
for _ , nxt := range next ( s ) {
if v , ok := dist [ nxt ]; ! ok || v > dist [ s ] + 1 {
dist [ nxt ] = dist [ s ] + 1
heap . Push ( & q , pair { dist [ nxt ] + f ( nxt ), nxt })
}
}
}
}
type pair struct {
v int
s string
}
type hp [] pair
func ( h hp ) Len () int { return len ( h ) }
func ( h hp ) Less ( i , j int ) bool {
a , b := h [ i ], h [ j ]
return a . v < b . v
}
func ( h hp ) Swap ( i , j int ) { h [ i ], h [ j ] = h [ j ], h [ i ] }
func ( h * hp ) Push ( v any ) { * h = append ( * h , v .( pair )) }
func ( h * hp ) Pop () any { a := * h ; v := a [ len ( a ) - 1 ]; * h = a [: len ( a ) - 1 ]; return v }
GitHub