키보드 행 Leetcode 솔루션


난이도 쉽게
자주 묻는 질문 Mathworks
해싱

문제 정책

이 문제에서 우리는 정렬 문자열 주어진 배열에서 어떤 문자열이 같은 행에 속하는지 찾아야합니다. QWERTY 아래와 같이 키보드 :

키보드 행 Leetcode 솔루션

배열에 영문 문자열이 포함되어 있다고 가정합니다.

String_Array = {"Anand" , "Soni" , "Ashfak" , "Turipo"}
Ashfaq Turipo
String_Array = {"qaz" , "wsx" , "edc"}
No words found

접근 (해싱)

접근 방식은 매우 간단합니다. 모든 인덱스를 행에 해시하고 배열의 모든 문자열에 대한 모든 문자가 해시 된 동일한 값을 가지고 있는지 확인할 수 있습니다. 그러나 해싱 부분을 사전 처리하려면 먼저 26 자 모두에 대해 해시해야합니다. 이를 바탕으로 배열에 저장하고 반환 할 수 있습니다.

암호알고리즘

  1. HashMap 만들기 rowId 및 배열 결과 결과 문자열 저장
  2. 부울 변수 초기화 same_row = true 문자열 검사 실행
  3. 모든 문자를 행에 해시
  4. 배열의 모든 문자열 str에 대해 :
    • same_row = true 설정
    • 모든 캐릭터를 위해 chr 배열에서 시작하는 둘째:
      • 경우 rowId [chr] 같지 않다 rowId [first_character] :
        • same_row = false로 설정하고 다음 문자열로 이동
    • same_row == true 인 경우 :
      • 밀어 결과
  5. 반환 결과

키보드 행 Leetcode 솔루션 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

vector <string> findWords(vector <string> &words)
{
    unordered_map <char , int> rowId;

    string temp = "qwertyuiopQWERTYUIOP";
    for(char &i : temp)
        rowId[i] = 1;

    temp = "asdfghjklASDFGHJKL";
    for(char &i : temp)
        rowId[i] = 2;

    temp = "zxcvbnmZXCVBNM";
    for(char &i : temp)
        rowId[i] = 3;

    bool same_row;

    vector <string> result;
    for(string &word : words)
    {
        same_row = true;
        for(int i = 1 ; i < word.size() ; i++)
        {
            if(rowId[word[i]] != rowId[word[0]])
            {
                same_row = false;
                break;
            }
        }
        if(same_row)
            result.push_back(word);
    }
    return result;
}

int main()
{
    vector <string> words = {"Anand" , "Soni" , "Ashfak" , "Turipo"};
    vector <string> result = findWords(words);
    for(string &word : result)
        cout << word << " ";
    return 0;
}

자바 프로그램

import java.util.*;

class keyboard_row
{
    public static void main(String args[])
    {
        String[] words = {"Anand" , "Soni" , "Ashfak" , "Turipo"};
        String result[] = findWords(words);
        for(String word : result)
            System.out.print(word + " ");
    }

    static String[] findWords(String[] words)
    {
        HashMap <Character , Integer> rowId = new HashMap <>();

        String temp = "qwertyuiopQWERTYUIOP";
        for(char i : temp.toCharArray())
            rowId.put(i , 1);

        temp = "asdfghjklASDFGHJKL";
        for(char i : temp.toCharArray())
            rowId.put(i , 2);

        temp = "zxcvbnmZXCVBNM";
        for(char i : temp.toCharArray())
            rowId.put(i , 3);

        boolean same_row;

        List <String> result_list = new ArrayList<String>();


        for(String word : words)
        {
            same_row = true;
            for(int i = 1 ; i < word.length() ; i++)
            {
                if(rowId.get(word.charAt(i)) != rowId.get(word.charAt(0)))
                {
                    same_row = false;
                    break;
                }
            }
            if(same_row)
                    result_list.add(word);
        }

        String[] result = new String[result_list.size()];
        for(int i = 0 ; i < result.length ; i++)
            result[i] = result_list.get(i);

        return result;
    }
}
Ashfak Turipo

키보드 행 Leetcode 솔루션의 복잡성 분석

시간 복잡성

의 위에) 배열에있는 모든 문자열의 모든 문자를 순회합니다. N = 모든 문자열 길이의 합계.

공간 복잡성

O (1) 우리는 기억에 관계없이 기억에 일정한 공간을 둡니다.