leetcode/algorithms/ruby/0859-buddy-strings.rb at main · remy727/leetcode · GitHub

Name: leetcode/algorithms/ruby/0859-buddy-strings.rb at main · remy727/leetcode · GitHub
Rating: 4.6 (9715 reviews)
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
# frozen_string_literal: true

# 859. Buddy Strings
# Easy
# https://leetcode.com/problems/buddy-strings

=begin
Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.
Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].
* For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:
Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

Example 2:
Input: s = "ab", goal = "ab"
Output: false
Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.

Example 3:
Input: s = "aa", goal = "aa"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.

Constraints:
* 1 <= s.length, goal.length <= 2 * 104
* s and goal consist of lowercase letters.
=end

# @param {String} s
# @param {String} goal
# @return {Boolean}
defbuddy_strings1(s,goal)
returnfalseifs.length != goal.length
returnfalseifs.size < 2

h={}
ans=[]
dublicates=false
s.chars.each_with_index{ |v,i|
dublicates=trueifh[v]
h[v]=true
returnfalseifans.size > 2
ans.push(i)ifv != goal[i]
}
returndublicatesifans.empty?
returnfalseifans.size != 2
i,j=ans
s[i] == goal[j] && s[j] == goal[i]
end

defbuddy_strings2(s,goal)
returnfalseifs.length != goal.length

s1=""
s2=""
chars=[].to_set
repeated=false

s.length.timesdo |i|
repeated ||= !chars.add?(s[i])
nextifs[i] == goal[i]
s1 += s[i]
s2 += goal[i]
end

(s1.length == 2 && s1 == s2.reverse) ||
(s1.length == 0 && repeated)
end

defbuddy_strings3(s,goal)
returnfalseifs.size != goal.size
d=s.chars.zip(goal.chars).each_with_index.inject([]){ |res,((c1,c2),idx)|
res << idxifc1 != c2
res
}
cased.size
when0then !s.chars.tally.filter{ |c,v| v >= 2}.empty?
when2thens[d.first] == goal[d.last] && s[d.last] == goal[d.first]
else
false
end
end

defbuddy_strings4(s,goal)
returnfalseifs.size != goal.size

s_uniq_chars=s.chars.uniq.sort
gogal_uniq_chars=goal.chars.uniq.sort

returnfalseifs_uniq_chars != gogal_uniq_chars

ifs == goal
s.size - s_uniq_chars.size >= 1
else
indices=[]
counter=0

s.size.timesdo |i|
ifs[i] != goal[i]
counter += 1
indices << i
end

returnfalseifcounter > 2
end

s[indices[0]] == goal[indices[1]] &&
s[indices[1]] == goal[indices[0]]
end
end

# **************** #
# TEST #
# **************** #

require"test/unit"
classTest_buddy_strings < Test::Unit::TestCase
deftest_
assert_equaltrue,buddy_strings4("ab","ba")
assert_equalfalse,buddy_strings4("ab","ab")
assert_equaltrue,buddy_strings4("aa","aa")
end
end

# ********************#
# Benchmark #
# ********************#

require"benchmark"

s="abcd"
goal="cbad"
Benchmark.bmdo |bm|
bm.report("buddy_strings1: "){buddy_strings1(s,goal)}
bm.report("buddy_strings2: "){buddy_strings2(s,goal)}
bm.report("buddy_strings3: "){buddy_strings3(s,goal)}
bm.report("buddy_strings4: "){buddy_strings4(s,goal)}
end

# user system total real
# buddy_strings1: 0.000032 0.000004 0.000036 ( 0.000029)
# buddy_strings2: 0.002619 0.000254 0.002873 ( 0.002903)
# buddy_strings3: 0.000639 0.000004 0.000643 ( 0.000641)
# buddy_strings4: 0.000022 0.000001 0.000023 ( 0.000021)