字母组合

一.题目

二.歧义

这题目文字描述和样例没有讲清楚：

1.是否要做输入的数字校验，因为有可能输入超过10的数字

2.输入的字符和数字之间一定用空格分隔，还是可以不分割。

三.解题思路

这道题剔除一些无关简要的代码，可以采用暴力排列组合，也可以采用动态规划。由于此题难度其实不大， 也不涉及背包问题，就采用了暴力的排列组合。

四.代码

1.先上主函数 。

• 先初始化加载关联字母。
• 输入cin
• 因为题目没有讲清楚输入是否一定采用空格分隔，这里做了切分和内部转换为数字
• 通过用户输入的数字获取哪些字母集合要进行排列
• 进行排列
• 剔除屏蔽的字符
• 输出结果

void main()
{
    InitDictionary();
    std::string numString;
    std::string ingnoreString;
    std::getline(std::cin ,numString);
    std::getline(std::cin, ingnoreString);
    std::cout << std::endl;

    std::string space = " ";
    //分割字符串
    std::vector<int> nums = SplitStringToDigit(numString, space);
    bool isContainSameDigit = IsContainSameDigit(nums);
    if (isContainSameDigit)
        return;
    std::vector<char> ignore = SplitString(ingnoreString, space);
    //做完校验，获取到用户输入的信息之后 就可以开始 排列组合 剔除掉受影响的组合即可。 这里可以用排列组合,也可以用动态规划的思维来解决问题
    std::vector<std::vector<char>> sources = GetDictionary(nums);
    std::vector<std::vector<char>> result=GetPermutation(sources, ignore);
    for (auto& vect : result)
    {
        std::string str;
        for (char c : vect)
        {
            str += c;
        }
        std::cout << str << std::endl;
    }
}

2.初始化关联字母

std::unordered_map<int, std::vector<char>> dictionary;
void InitDictionary()
{
    std::vector<char> v0 = { 'a','b','c' };
    std::vector<char> v1 = { 'd','e','f' };
    std::vector<char> v2 = { 'g','h','i' };
    std::vector<char> v3 = { 'j','k','l' };
    std::vector<char> v4 = { 'm','n','o' };
    std::vector<char> v5 = { 'p','q','r' };
    std::vector<char> v6 = { 's','t' };
    std::vector<char> v7 = { 'u','v' };
    std::vector<char> v8 = { 'w','x' };
    std::vector<char> v9 = { 'y','z' };
    dictionary.insert(std::make_pair(0, v0));
    dictionary.insert(std::make_pair(1, v1));
    dictionary.insert(std::make_pair(2, v2));
    dictionary.insert(std::make_pair(3, v3));
    dictionary.insert(std::make_pair(4, v4));
    dictionary.insert(std::make_pair(5, v5));
    dictionary.insert(std::make_pair(6, v6));
    dictionary.insert(std::make_pair(7, v7));
    dictionary.insert(std::make_pair(8, v8));
    dictionary.insert(std::make_pair(9, v9));
}

3.切分

//如果字符串包含指定字符，则分割之后转换为数字。 不包含则按位切分
std::vector<int> SplitStringToDigit(std::string str, const std::string& reg)
{
    std::vector<int> result;
    if (str.find(reg) == std::string::npos)
    {
        for (char c : str)
        {
            result.push_back(c - '0');
        }
        return result;
    }
    else
    {
        std::string::size_type posLast = 0;
        std::string::size_type posCurrent = str.find(reg);

        while (posCurrent != std::string::npos)
        {
            result.push_back(str.substr(posLast, posCurrent - posLast).c_str()[0] - '0');
            posLast = posCurrent + reg.size();
            posCurrent = str.find(reg, posLast);
        }

        if (posLast < str.length())
        {
            result.push_back(str.substr(posLast).c_str()[0] - '0');
        }
    }
    return result;
}
//题目也没有说输入的字符是否以空格排列， 此处考虑空格间隔情况
std::vector<char> SplitString(std::string str, const std::string& reg)
{
    std::vector<char> result;
    if (str.find(reg) == std::string::npos)
    {
        for (char c : str)
        {
            result.push_back(c);
        }
        return result;
    }
    else
    {
        std::string::size_type posLast = 0;
        std::string::size_type posCurrent = str.find(reg);

        while (posCurrent != std::string::npos)
        {
            result.push_back(str.substr(posLast, posCurrent - posLast).c_str()[0]);
            posLast = posCurrent + reg.size();
            posCurrent = str.find(reg, posLast);
        }

        if (posLast < str.length())
        {
            result.push_back(str.substr(posLast).c_str()[0]);
        }
    }
    return result;
}

4.排列

//std::vector<std::vector<char>> 为一个动态的二维数组，一维指的是用户输入的数字， 二维指的是输入的数字所关联的字符
//  i这里表示的是一维索引位置。  j表示的是二维索引位置
void GetPermuatations(int i,int j,std::vector<std::vector<char>>& sources, std::vector<std::vector<char>>& pers)
{
    //如果超过了限定，就退出，避免递归死循环
    if (i >= sources.size()) return;
    if (i == 0 && j == 0)
    {
        for (int k = 0; k < sources[i].size(); k++)
        {
            std::vector<char> vs;
            vs.push_back(sources[i][k]);
            pers.push_back(vs);
        }
    }
    else
    {
        //在上一轮的排列结果至上 继续进行新的元素的排列
        std::vector<std::vector<char>> newPers;
        for (auto& vect : pers)
        {
            for (int k = 0; k < sources[i].size(); k++)
            {
                std::vector<char> vs(vect);
                vs.push_back(sources[i][k]);
                newPers.push_back(vs);
            }
        }
        pers.clear();
        pers = newPers;
    }
    GetPermuatations(++i, ++j, sources, pers);
}
//字符集合 是否连续存在被忽略的字符信息
bool IsIgnore(const std::vector<char>& chrs, std::vector<char>& ignore)
{
    std::sort(ignore.begin(), ignore.end());
    if (chrs.size() < ignore.size())
        return false;
    
    char first = *ignore.begin();
    auto iter=std::find(chrs.begin(), chrs.end(), first);
    if (iter == chrs.end())
        return false;
    int start = std::distance(chrs.begin(), iter);
    for (int i = start; i < ignore.size(); i++)
    {
        if (chrs[i] != ignore[i - start])
            return false;
    }
    return true;
}
//字母组合的核心函数
std::vector<std::vector<char>> GetPermutation(std::vector<std::vector<char>>& sources, std::vector<char>& ignore)
{
    std::vector<std::vector<char>> pers;
    GetPermuatations(0,0, sources, pers);

    std::vector<std::vector<char>> result;
    //剔除掉被忽略的场景
    for (auto& vect : pers)
    {
        if (!IsIgnore(vect, ignore))
        {
            result.push_back(vect);
        }
    }
    return result;
}

完整代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
#include <string>
#include <algorithm>

#pragma region 11
//如果字符串包含指定字符，则分割之后转换为数字。 不包含则按位切分
std::vector<int> SplitStringToDigit(std::string str, const std::string& reg)
{
    std::vector<int> result;
    if (str.find(reg) == std::string::npos)
    {
        for (char c : str)
        {
            result.push_back(c - '0');
        }
        return result;
    }
    else
    {
        std::string::size_type posLast = 0;
        std::string::size_type posCurrent = str.find(reg);

        while (posCurrent != std::string::npos)
        {
            result.push_back(str.substr(posLast, posCurrent - posLast).c_str()[0] - '0');
            posLast = posCurrent + reg.size();
            posCurrent = str.find(reg, posLast);
        }

        if (posLast < str.length())
        {
            result.push_back(str.substr(posLast).c_str()[0] - '0');
        }
    }
    return result;
}
#pragma endregion 
//题目也没有说输入的字符是否以空格排列， 此处考虑空格间隔情况
std::vector<char> SplitString(std::string str, const std::string& reg)
{
    std::vector<char> result;
    if (str.find(reg) == std::string::npos)
    {
        for (char c : str)
        {
            result.push_back(c);
        }
        return result;
    }
    else
    {
        std::string::size_type posLast = 0;
        std::string::size_type posCurrent = str.find(reg);

        while (posCurrent != std::string::npos)
        {
            result.push_back(str.substr(posLast, posCurrent - posLast).c_str()[0]);
            posLast = posCurrent + reg.size();
            posCurrent = str.find(reg, posLast);
        }

        if (posLast < str.length())
        {
            result.push_back(str.substr(posLast).c_str()[0]);
        }
    }
    return result;
}

//集合中是否包含相同的元素 true:包含相同的元素
bool IsContainSameDigit(const std::vector<int>& nums)
{
    std::set<int> se;
    for (int i : nums)
    {
        se.insert(i);
    }
    if (se.size() != nums.size())
        return true;
    else
        return false;
}

//std::vector<std::vector<char>> 为一个动态的二维数组，一维指的是用户输入的数字， 二维指的是输入的数字所关联的字符
//  i这里表示的是一维索引位置。  j表示的是二维索引位置
void GetPermuatations(int i,int j,std::vector<std::vector<char>>& sources, std::vector<std::vector<char>>& pers)
{
    //如果超过了限定，就退出，避免递归死循环
    if (i >= sources.size()) return;
    if (i == 0 && j == 0)
    {
        for (int k = 0; k < sources[i].size(); k++)
        {
            std::vector<char> vs;
            vs.push_back(sources[i][k]);
            pers.push_back(vs);
        }
    }
    else
    {
        //在上一轮的排列结果至上 继续进行新的元素的排列
        std::vector<std::vector<char>> newPers;
        for (auto& vect : pers)
        {
            for (int k = 0; k < sources[i].size(); k++)
            {
                std::vector<char> vs(vect);
                vs.push_back(sources[i][k]);
                newPers.push_back(vs);
            }
        }
        pers.clear();
        pers = newPers;
    }
    GetPermuatations(++i, ++j, sources, pers);
}

//字符集合 是否连续存在被忽略的字符信息
bool IsIgnore(const std::vector<char>& chrs, std::vector<char>& ignore)
{
    std::sort(ignore.begin(), ignore.end());
    if (chrs.size() < ignore.size())
        return false;
    
    char first = *ignore.begin();
    auto iter=std::find(chrs.begin(), chrs.end(), first);
    if (iter == chrs.end())
        return false;
    int start = std::distance(chrs.begin(), iter);
    for (int i = start; i < ignore.size(); i++)
    {
        if (chrs[i] != ignore[i - start])
            return false;
    }
    return true;
}

//字母组合的核心函数
std::vector<std::vector<char>> GetPermutation(std::vector<std::vector<char>>& sources, std::vector<char>& ignore)
{
    std::vector<std::vector<char>> pers;
    GetPermuatations(0,0, sources, pers);

    std::vector<std::vector<char>> result;
    //剔除掉被忽略的场景
    for (auto& vect : pers)
    {
        if (!IsIgnore(vect, ignore))
        {
            result.push_back(vect);
        }
    }
    return result;
}


std::unordered_map<int, std::vector<char>> dictionary;
void InitDictionary()
{
    std::vector<char> v0 = { 'a','b','c' };
    std::vector<char> v1 = { 'd','e','f' };
    std::vector<char> v2 = { 'g','h','i' };
    std::vector<char> v3 = { 'j','k','l' };
    std::vector<char> v4 = { 'm','n','o' };
    std::vector<char> v5 = { 'p','q','r' };
    std::vector<char> v6 = { 's','t' };
    std::vector<char> v7 = { 'u','v' };
    std::vector<char> v8 = { 'w','x' };
    std::vector<char> v9 = { 'y','z' };
    dictionary.insert(std::make_pair(0, v0));
    dictionary.insert(std::make_pair(1, v1));
    dictionary.insert(std::make_pair(2, v2));
    dictionary.insert(std::make_pair(3, v3));
    dictionary.insert(std::make_pair(4, v4));
    dictionary.insert(std::make_pair(5, v5));
    dictionary.insert(std::make_pair(6, v6));
    dictionary.insert(std::make_pair(7, v7));
    dictionary.insert(std::make_pair(8, v8));
    dictionary.insert(std::make_pair(9, v9));
}

std::vector<std::vector<char>> GetDictionary(const std::vector<int>& nums)
{
    std::vector<std::vector<char>> result;
    for (int i : nums)
    {
        result.push_back(dictionary[i]);
    }
    return result;
}

void main()
{
    InitDictionary();
    std::string numString;
    std::string ingnoreString;
    std::getline(std::cin ,numString);
    std::getline(std::cin, ingnoreString);
    std::cout << std::endl;

    std::string space = " ";
    //分割字符串
    std::vector<int> nums = SplitStringToDigit(numString, space);
    bool isContainSameDigit = IsContainSameDigit(nums);
    if (isContainSameDigit)
        return;
    std::vector<char> ignore = SplitString(ingnoreString, space);

    //做完校验，获取到用户输入的信息之后 就可以开始 排列组合 剔除掉受影响的组合即可。 这里可以用排列组合,也可以用动态规划的思维来解决问题
    std::vector<std::vector<char>> sources = GetDictionary(nums);

    std::vector<std::vector<char>> result=GetPermutation(sources, ignore);

    for (auto& vect : result)
    {
        std::string str;
        for (char c : vect)
        {
            str += c;
        }
        std::cout << str << std::endl;
    }
}