java - 创建单词转换图

Question

我正在尝试从字典中创建一个单词图表，其中图表中的相邻单词应该符合以下两条规则中的任何一条：1）其中一个单词还有一个字符，如果没有那个额外的字符，它们是相同的 2）长度相等，除一个字母外相同（一个字符替换）

我写了 2 种方法来创建图表。

使用第一条规则的第一个（addLadder）工作正常：但是我在使用第二条规则的第二种方法（addEq）时遇到问题：

 public static void addLadder(){

        for(Map.Entry<Integer,Set<String>> e:theMap.entrySet())
        {
            int theWordLen = e . getKey ( ) ;
            Set<String>theWords = e.getValue( );
         if(theWordLen>1){
            Set<String>shorterWords = theMap.get(theWordLen-1);
            for(String s :theWords)
            {
                for(int i=0; i<theWordLen ; i++)
                {
                    String shorter = removeOneChar (s,i);
                    if(shorterWords.contains( shorter ) )
                    {
                        addEdge(s,shorter,s.length());
                        addEdge(shorter,s,s.length());
                    }
                }
            }
          } 
        }
    }





 public static void addEq(){

        for(Map.Entry<Integer,Set<String>> e:theMap.entrySet())
        {
            int theWordLen = e.getKey ( ) ;
            Set<String>theWords = e.getValue( );
            for(int i=0; i<theWordLen ; i++)
            {

                Map<String , List<String>>repMap = new TreeMap<String , List<String>>();
                List<String> myList = new ArrayList<String>();
                for(String w:theWords  )
                {
                    String shorter = removeOneChar(w,i);
                    myList.add(shorter);
                    repMap.put(w, myList);

                }

    }
}

}

感谢您的任何提示。

Answer 1

只要编辑距离为 1，只需检查每个字符的单词字符：例如：

private boolean ruleTwo (String s1, String s2)
{
    if (s1.length() != s2.length())
        return false;


    int different = 0;
    for (int i=0; i<s1.length() && different <= 1; i++)
    {
        if (s1.charAt(i) != s2.charAt(i))
            different ++;
    }

    return different == 1;
}