C++LeetCode(17.전화번호 의 알파벳 조합)실현

[LeetCode]17.Letter Combinations of a Phone Number 전화번호 의 알파벳 조합
Given a string containing digits from 2-9inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
이 문 제 는 전화번호 의 알파벳 조합,즉 숫자 2 에서 9 까지 의 모든 숫자 가 몇 개의 알파벳 을 대표 할 수 있 는 지 를 구 한 다음 에 한 줄 의 숫자 를 주 고 가능 한 모든 조합 을 구 할 수 있 도록 한다.재 귀적 Recursion 으로 풀 수 있 습 니 다.하나의 사전 을 만들어 서 모든 숫자 가 대표 하 는 문자열 을 저장 해 야 합 니 다.그리고 하나의 변수 level 이 필요 합 니 다.현재 생 성 된 문자열 의 문자 개 수 를 기록 하고 세트 는 상기 문제 와 매우 유사 합 니 다.재 귀 함수 에서 level 을 먼저 판단 하고 digits 의 숫자 갯 수 와 같 으 면 현재 조합 을 결과 res 에 넣 고 되 돌려 줍 니 다.우 리 는 digits 의 숫자 를 통 해 dict 에서 문자열 을 추출 한 다음 에 이 추출 한 문자열 을 옮 겨 다 니 며 모든 문 자 를 현재 조합 뒤에 추가 하고 재 귀 함 수 를 호출 하면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> res;
        vector<string> dict{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        letterCombinationsDFS(digits, dict, 0, "", res);
        return res;
    }
    void letterCombinationsDFS(string& digits, vector<string>& dict, int level, string out, vector<string>& res) {
        if (level == digits.size()) {res.push_back(out); return;}
        string str = dict[digits[level] - '0'];
        for (int i = 0; i < str.size(); ++i) {
            letterCombinationsDFS(digits, dict, level + 1, out + str[i], res);
        }
    }
};
이 문 제 는 반복 Iterative 로 풀 수 있 습 니 다.digits 의 모든 숫자 를 옮 겨 다 닐 때 임시 문자열 배열 t 를 만 든 다음 에 위의 해법 과 같이 숫자 를 통 해 dict 에서 문자열 str 를 꺼 낸 다음 문자열 의 모든 문 자 를 옮 겨 다 니 며 현재 결과 res 의 모든 문자열 을 옮 겨 다 니 며 문 자 를 뒤에 추가 합 니 다.임시 문자열 배열 t 에 추가 합 니 다.추출 한 문자열 str 를 옮 겨 다 닌 후 임시 문자열 배열 을 결과 res 에 할당 합 니 다.구체 적 으로 참조 코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> res{""};
        vector<string> dict{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for (int i = 0; i < digits.size(); ++i) {
            vector<string> t;
            string str = dict[digits[i] - '0'];
            for (int j = 0; j < str.size(); ++j) {
                for (string s : res) t.push_back(s + str[j]);
            }
            res = t;
        }
        return res;
    }
};
C++구현 LeetCode(17.전화번호 의 알파벳 조합)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 C++구현 전화번호 의 알파벳 조합 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 읽 어 주시 기 바 랍 니 다.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!

좋은 웹페이지 즐겨찾기