检查两个字符串是否同构

Question

我试图解决一个问题来确定两个字符串是否是同构的。当字符串中的每个字符都可以替换为字符串2中的另一个字符时，它们是同构的。两个不同的字符可能不能映射到相同的值，而相同的字符不能与不同的值匹配。此外，字符串的长度必须相同。

我对逻辑流使用了异常：

module Isomorphism

  class NotIsomorphicException < StandardError
    attr_reader :object
    def initialize(object)
      @object = object
    end
  end

  def self.isomorphic? string_a,string_b
    begin
      self.isomorphism string_a,string_b
      true
    rescue NotIsomorphicException => _
      return false
    end
  end

  protected
  def self.isomorphism string_a,string_b
    raise NotIsomorphicException.new("Unequal length") unless string_a.size == string_b.size

    isomorphism_map = {}
    associations = string_a.chars.zip string_b.chars

    associations.each do |char_one,char_two|
      if(isomorphism_map.key? char_one)
        raise NotIsomorphicException.new("Single character needs to map to multiple characters, not isomorphic") unless isomorphism_map[char_one] == char_two
      elsif(isomorphism_map.value? char_two)
        raise NotIsomorphicException.new("Two characters map to same value")
      end
      isomorphism_map[char_one] = char_two
    end
  end

end

请让我知道，如果它是可以这样编码和任何改进，我可能能够使这更好。

以下是规格，以防万一：

describe Isomorphism do
  it "should return true for single character words" do
    expect(Isomorphism.isomorphic? "t","d").to be true
  end

  it "should return true for empty strings" do
    expect(Isomorphism.isomorphic? "","").to be true
  end

  it "should return false if strings are of unequal length" do
    expect(Isomorphism.isomorphic? "dh","dhruv").to be false
  end

  it "should return false when 2 characters need to map to same character" do
    expect(Isomorphism.isomorphic? "ab","aa").to be false
  end

  it "should return true for egg and add" do
    expect(Isomorphism.isomorphic? "egg","add").to be true
  end

  it "should return false for foo and bar" do
    expect(Isomorphism.isomorphic? "foo","bar").to be false
  end

  it "should return true for paper and title" do
    expect(Isomorphism.isomorphic? "paper","title").to be true
  end

  it "should return false for aab and aaa" do
    expect(Isomorphism.isomorphic? "aab","aaa").to be false
  end
end

Answer 1

查看您的isomorphism助手函数…

控制的流程有点恶心。特别是，将一个unless埋在这里…

if …
  raise Exception.new(…) unless …
elsif …
  raise
end

…太棘手了，因为：

• 您已经有了一个if-elsif表达式，最好将其工作在同一个链中。
• 它在一条很长的线的尽头，在那里几乎看不见。
• unless是否定的，它比肯定的if更不可取。

将命名约定从string_a、string_b切换到char_one、char_two并不理想。为什么不是char_a，char_b？或者更好，只有a，b？

反向使用Hash进行value?查找是不有效的。你最好做一张“正”图和一张“逆”图。下面是一个更好的分解问题的方法。

至于内部使用异常，我认为这是个坏主意。这只是一个麻烦的方式，return false与评论。您可以只写一个注释，以避免开销。更好的是，如果你写的代码很好，我不认为有任何评论的必要。例如，在下面的实现中，b != expected_b是非常清楚的。

module Isomorphism

  def self.isomorphic?(string_a, string_b)
    surjective?(string_a, string_b) && surjective?(string_b, string_a)
  end

  protected
  def self.surjective?(string_a, string_b)
    return false if string_a.size != string_b.size
    surjection = {}

    string_a.chars.zip(string_b.chars).each do |a, b|
      expected_b = surjection[a]
      if expected_b && (b != expected_b)
        return false
      end
      surjection[a] = b
    end
    true
  end

  # Alternate implementation: shorter, but won't detect failure as quickly
  def self.surjective?(string_a, string_b)
    return false if string_a.size != string_b.size
    pairs = string_a.chars.zip(string_b.chars)
    surjection = Hash[pairs]
    pairs.all? { |a, b| surjection[a] == b }
  end

end

Answer 2

我并不经常将代码评审与此相匹配，但我发现这个问题很有趣，如果不使用.zip和{}，就可以解决这个问题：

def isomorphic? a, b

  each_char_positions = lambda do |string|
    string.each_char.map.with_index.group_by(&:first).
      map{ |c, poss| poss.map(&:last) }.sort
  end

  each_char_positions[a] == each_char_positions[b]

end

如果字符串的唯一字符位置的数组相同，则字符串是同构的。您可以在tap{ |s| p s }.后插入group_by行，以查看“纸张”与“标题”之间的关系：

{"p"=>[["p", 0], ["p", 2]], "a"=>[["a", 1]], "e"=>[["e", 3]], "r"=>[["r", 4]]}  
{"t"=>[["t", 0], ["t", 2]], "i"=>[["i", 1]], "l"=>[["l", 3]], "e"=>[["e", 4]]}