为什么字符串按字母顺序排序？

Question

这是Leetcode804：独一无二的莫尔斯电码。我想知道为什么我的代码给出了正确的摩尔斯电码，但它是按字母顺序排序的，这不是故意的。感谢您的任何贡献

输入：

words = ["gin", "zen", "gig", "msg"]

代码：

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        morse = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
        alphabet = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
        transformation = []
        zip_ = list(zip(morse, alphabet))
        for word in words:
            transformation.append(''.join(code[0] for code in zip_ for letter in word if letter in code[1]))

输出：

['--...-.', '.-.--..', '--.--...', '--.--...']    

Answer 1

问题是，您首先遍历zip文件，然后遍历字母。这就是造成字母顺序zip_uu按字母顺序排序的原因

此版本执行您希望它执行的操作：

 class Solution: 
      def uniqueMorseRepresentations(self, words: List[str]) -> int: 
          morse = [".-","-...","-.-.","-..",".","..-."," .","....","..",". -","-.-",".-.."," ","-."," -",". ."," .-",".-.","...","-","..-","...-",". ","-..-","-. "," .."] 
          alphabet = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'] 
          transformation = [] 
          zip_ = list(zip(morse, alphabet)) 
          for word in words: 
              transformation.append(''.join(code[0] for letter in word for code in zip_  if letter in code[1]))

这并不是最符合python的方式，但它是对您的解决方案的最小修复

就个人而言，我会使用字典将字母映射到摩尔斯电码，然后遍历字符串的字符。这有点类似于https://stackoverflow.com/users/6553328/emma的解决方案，但对于不知道字符整数值的人来说更容易阅读

Answer 2

不确定您所面临的问题，这将通过：

class Solution:
    def uniqueMorseRepresentations(self, words):
        morse_map = [".-", "-...", "-.-.", "-..", ".", "..-.", " .", "....", "..", ". -", "-.-", ".-..", " ",
             "-.", " -", ". .", " .-", ".-.", "...", "-", "..-", "...-", ". ", "-..-", "-. ", " .."]
        return len({''.join(morse_map[ord(char) - 97] for char in word) for word in words})

97是ord('a')：

class Solution:
    def uniqueMorseRepresentations(self, words):
        morse_map = [".-", "-...", "-.-.", "-..", ".", "..-.", " .", "....", "..", ". -", "-.-", ".-..", " ",
             "-.", " -", ". .", " .-", ".-.", "...", "-", "..-", "...-", ". ", "-..-", "-. ", " .."]
        return len({''.join(morse_map[ord(char) - ord('a')] for char in word) for word in words})

我在您的解决方案中没有看到return语句或set()。有两个简单的步骤：

• 将访问的转换添加到集合中
• 返回集合的长度

---

如果您感兴趣，这里还有一个使用哈希集的Java版本（类似于Python中的set()）：

public final class Solution {
    public static final int uniqueMorseRepresentations(
        final String[] words
    ) {
        final String[] morseMap = {".-", "-...", "-.-.", "-..", ".", "..-.", " .", "....", "..", ". -", "-.-", ".-..", " ", "-.", " -", ". .", " .-", ".-.", "...", "-", "..-", "...-", ". ", "-..-", "-. ", " .."};
        Set<String> transformations = new HashSet<>();

        for (String word : words) {
            StringBuilder transformation = new StringBuilder();

            for (int index = 0; index < word.length(); index++)
                transformation.append(morseMap[word.charAt(index) - 97]);

            transformations.add(transformation.toString());
        }

        return transformations.size();
    }
}

---

参考资料

• 有关更多详细信息，请参见Discussion Board，在那里您可以找到大量解释良好的、具有各种languages的公认解决方案，包括低复杂度算法和渐近runtime/memory分析^1，2