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

Question

这是来自Leetcode 804的题目：唯一摩尔斯密码词。我想知道为什么我的代码得到了正确的摩尔斯码，但它按字母顺序排序，这并不是我的本意。感谢任何帮助。

输入：

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]))

输出:

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

- delalma

Answer 1

问题在于您首先遍历zip_，然后再遍历字母。这就是导致字母排序的原因——zip_ 是按字母顺序排序的。

这个版本做到了你想要的：

 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 的解决方案，但对于不知道字符整数值的人来说更容易阅读。

- Robby the Belgian

---

非常好的回答，只有一个小备注：我相信如果您只发布更改的单行代码，您的答案将会更清晰、更简洁。由于更改实际上非常微小，它会被其他代码所掩盖，这使得找到实际修复变得困难... - Tomerikoo

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 is 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()。有两个简单的步骤：

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

---

这里还有一个使用 HashSet 的 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();
    }
}

---

参考资料

• 如需更多详细信息，请查看讨论板，您可以在那里找到大量解释清晰的已接受解决方案，包括低复杂度算法和渐进运行时间/内存分析，还有各种语言^{1, 2}。

- Emma