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;
}