leetcode17

今天药忘吃喽~ 2022-08-09 02:21 138阅读 0赞

LeetCode---Letter Combinations of a Phone Number

这道题目需要明确的就是，当参数string digits的长度为K时，最终子串的长度就是K，这是递归调用的返回条件<完成一种组合>

简单说明一下题意：

就是手机的九宫格输入法中，数字对应了不同的字母串

在代码中，我用Map来表示这种对应关系：

map<char,string>myMap;
    myMap['2']="abc";
    myMap['3']="def";
    myMap['4']="ghi";
    myMap['5']="jkl";
    myMap['6']="mno";
    myMap['7']="pqrs";
    myMap['8']="tuv";
    myMap['9']="wxyz";

现在给定一串数字输入，求字母的所有可能组合，上面说过，输入子串的长度，及结果集中子串的长度。

那么如，当输入"23"，长度为2，则结果集中的"ad""ae""af"等长度都是2。

基于这个条件，我们对输入的数字串进行递归调用，每次往临时子串变量temp中，添加当前数字对应的字串中的一个字母，并且每当完成一组子串后，将其添加到结果集的同时，将临时变量temp弹出上一个字符，深度优先搜索。

代码：

class Solution {
    private:
    	void MyFunc(string digits,string temp,vector<string> &result,map<char,string>myMap)
    	{
    		int i;
    		int currLen=temp.size();
    		if(currLen == digits.size())
    		{
    			result.push_back(temp);
    		//	temp.clear();
    		}
    		else
    		{
    			for(i = 0;i < myMap[ digits[currLen] ].size();i++)
    			{
    				temp = temp + myMap[ digits[currLen] ][i];
    				MyFunc(digits,temp,result,myMap);
    				temp.pop_back();
    			}
    		}
    	}
    public:
        vector<string> letterCombinations(string digits) {
    		vector<string>result;
    		string temp="";
    		if(digits.size()<1)
    		{
    			return result;
    		}
    		map<char,string>myMap;
    		myMap['2']="abc";
    		myMap['3']="def";
    		myMap['4']="ghi";
    		myMap['5']="jkl";
    		myMap['6']="mno";
    		myMap['7']="pqrs";
    		myMap['8']="tuv";
    		myMap['9']="wxyz";
    		MyFunc(digits,temp,result,myMap);
    		return result;
        }
    };