500. Keyboard Row

Description

Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.

Note that the strings are case-insensitive, both lowercased and uppercased of the same letter are treated as if they are at the same row.

In the American keyboard:

• the first row consists of the characters "qwertyuiop",
• the second row consists of the characters "asdfghjkl", and
• the third row consists of the characters "zxcvbnm".

Example 1:

• Input: words = [“Hello”,”Alaska”,”Dad”,”Peace”]
• Output: [“Alaska”,”Dad”]
• Explanation: Both “a” and “A” are in the 2nd row of the American keyboard due to case insensitivity.

Example 2:

• Input: words = [“omk”]
• Output: []

Example 3:

• Input: words = [“adsdf”,”sfd”]
• Output: [“adsdf”,”sfd”]

Constraints:

• 1 <= words.length <= 20
• 1 <= words[i].length <= 100
• words[i] consists of English letters (both lowercase and uppercase).

Submitted Code

class Solution(object):
    def findWords(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        row1, row2, row3 = "qwertyuiop", "asdfghjkl", "zxcvbnm"
        result = []

        for i in range(len(words)):
            w = list(words[i])      # 각 단어를 리스트로 변경
            same_row = True

            for j in range(len(w)):
                if w[j].lower() in row1:
                    w[j] = 1
                elif w[j].lower() in row2:
                    w[j] = 2
                elif w[j].lower() in row3:
                    w[j] = 3
                
                if j != 0 and w[j-1] != w[j]:   # 첫 번째 글자가 아니고 그 앞의 글자와 다를 경우
                    same_row = False
                    break
            
            if same_row:
                result.append(words[i])
        
        return result

Runtime: 0 ms | Beats 100.00%
Memory: 12.30 MB | Beats 80.47%

각 단어를 리스트로 변경한 후, 그 전의 글자가 어떤 줄에 속해있는지 비교하는 방법을 사용했다. 코드는 복잡하지만 줄이 다른 글자가 초반에 나올 경우 바로 빠져나오기 때문에 런타임이 빨랐던 것 같다.

Other Solutions

1st

        map = { 'q':1,'w':1,'e':1,'r':1,'t':1,'y':1,'u':1,'i':1,'o':1,'p':1,
                'a':2,'s':2,'d':2,'f':2,'g':2,'h':2,'j':2,'k':2,'l':2,
                'z':3,'x':3,'c':3,'v':3,'b':3,'n':3,'m':3 }
        
        result = list()
        for word in words:
            row = set()
            for c in word:
                row.add(map[c.lower()])
                
            if len(row) == 1:
                result.append(word)
        
        return result 

time complexity: 𝑂(𝑛*𝑚) ← 각 단어마다 n번, 각 글자마다 m번 반복
space complexity: 𝑂(𝑛)

해시 테이블과 set()을 이용한 방법이다. 해당 단어에 포함된 줄 번호만 추출하기 때문에 한 줄로만 작성 가능한 단어일 경우 길이가 1이 된다.

2nd

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        l1="qwertyuiop"
        l2="asdfghjkl"
        l3="zxcvbnm"
        res=[]
        for word in words:
            w=word.lower()
            if len(set(l1+w))==len(l1) or len(set(l2+w))==len(l2) or len(set(l3+w))==len(l3) :
                res.append(word)
        return res

중첩 반복문 없이 풀 수도 있다.