Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
require 'set'
require 'pp'
def is_similar(s1, s2)
# fast path
if Set.new(s1.chars) != Set.new(s2.chars)
return false
elsif s1.size <= 2
return true
end
s1.chars.each_with_index do |c, i|
next if i == 0 || i == s1.size - 1
s1_1 = s1.chars.slice(0, i)
s1_2 = s1.chars.slice(i, 1e9)
s2_1 = s2.chars.slice(0, s1.size - i)
s2_2 = s2.chars.slice(s1.size - i, 1e9)
# 左-右 右-左
if Set.new(s1_1) == Set.new(s2_2) && is_similar(s1_1.join, s2_2.join) && is_similar(s2_1.join, s1_2.join)
return true
end
# 左-左 右-右
s1_1 = s1.chars.slice(0, i)
s1_2 = s1.chars.slice(i, 1e9)
s2_1 = s2.chars.slice(0, i)
s2_2 = s2.chars.slice(i, 1e9)
if Set.new(s1_1) == Set.new(s2_1) && is_similar(s1_1.join, s2_1.join) && is_similar(s2_2.join, s1_2.join)
return true
end
end
return false
end
p is_similar('ab', 'ba')
p is_similar('abc', 'bca')
p is_similar('bdc', 'bcd')
p is_similar('abcd', 'bdca')
p is_similar('abcd', 'bdac')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.