面试问题 - 基于映射的设计,用于实现检查文件中同构单词的代码。有效的方法。
如果一个单词中的字母可以重新映射以获得第二个单词,则两个单词被称为同构。
如果有 n 个单词,那么我能想到的最好方法是 O(n ^2 log n) 时间复杂度(n 个单词 - 对单词进行排序 - n log n - 并存储在 HashMap 中 - 空间复杂度 O(n ))。
如果文件很大,那么我们可以一次加载一半。
最佳答案
您可以将每个字母映射到一个素数,取出每个单词并找到其字母的乘积,然后检查哪些单词组成相同的因式分解。
这需要对每个字母进行 1 次乘法,并将每个单词插入产品 map 1 次。
关于java - 同构词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36959388/