Skip to content

Latest commit

 

History

History

1554.Strings-Differ-by-One-Character

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

1554.Strings-Differ-by-One-Character

考虑这个例子:{123,124,134,213}. 如何快速判断是否有两个数字只差别一个digit?

比较简单的方法就是:抹去所有的个位数,查看剩下的数值{120,120,130,210},将它们一次加入集合,就可以判断出是否有重复元素。如果没有发现,我们可以抹去十位数,得到的是{103,104,104,203},同理可以判断是否有重复元素... 对于任何位置的digit,我们一旦发现抹去之后剩余的数值有重复,那么就意味着至少有一对数字只差别这一位digit。

本题就是把上述思想扩展到字符串。用rolling hash的方法给每个字符串完整编码。然后逐位考察每一位的数字,将每个字符串的完整编码抹去那一位的编码,查看剩下的编码是否有重复即可。