1、电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

17_telephone_keypadLeetCode.png

示例:
输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:

尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。

题解

看完题目就知道这题是一道搜索题,枚举所有情况,类似 排列组合。首先先用个string数组存储所有数字到字母的映射,然后进行回溯操作。

回溯过程中维护一个字符串cur,表示当前的字母排列,该字符串初始化为空串。每次取电话号码中的一位数字,从string数组中获取该数字对应的所有可能的字母,并将其中的一个字母加入到当前的字母排列后面,然后继续处理电话号码的后一位数字,直到处理完电话号码中的所有数字,即得到一个完整的字母排列。然后进行回退操作,遍历其余的字母排列。

代码

class Solution {
public:
    
    string chars[8] = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return vector<string>();
        int n = digits.size();
        
        vector<string> res;

        dfs(res, digits, "", digits[0], 0, n);

        return res;
    }

    void dfs(vector<string>& res, string digits, string cur, char ch, int cnt, int n) {
        if (cnt == n) {
            res.push_back(cur);
            return;
        }
        for (auto& c : chars[ch - '2']) {
            dfs(res, digits, cur + c, digits[cnt + 1], cnt + 1, n);
        }
    }
};

要是觉得搜索不是很懂的话,也可以用迭代来写

class Solution {
public:
    
    string chars[8] = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return vector<string>();
        int n = digits.size();
        vector<string> state(1, "");
        vector<string> res;
        for (auto& u : digits) {
            vector<string> now;
            for (auto& v : chars[u - '2']) {
                for (auto& s : state) {
                    now.push_back(s + v);
                }
            }
            state = now;
        }
        return state;
    }
};

原题链接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/


2、单词搜索

题目描述

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
提示:

boardword 中只包含大写和小写英文字母。

  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200
  • 1 <= word.length <= 10^3

题解

一道纯暴搜加回溯的题。对于走过的元素是否使用过,这里开一个book数组来对走过的元素做标记。

1、首先遍历board的所有元素,找到和word第一个字符相同的元素,然后从当前下标位置开始搜索,设这个坐标为(i, j),搜索前先把该下标对应的位置做好标记。

book[i][j] = 1

2、接下来进入搜索,主要就是几件事:

  1. (i, j)出发,试探当前位置的上下左右位置的元素是否和word的下一个元素匹配
    • 若匹配,则继续搜索
    • 若不匹配,则直接返回false
  2. word所有字符都匹配完成后,返回true
注意
  • 下标要判断是否越界
  • 下一步不能走了记得回溯也就是清除标记
  • 还有return语句的位置要写对

代码

class Solution {
private:
    int dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, - 1} };
    int book[205][205] = { 0 };
    bool res = false;
public:
    bool dfs(int x, int y, int cur, vector<vector<char>>& board, string word) {
        if (cur == word.size()) return true;
        if (cur >= word.size()) return false;
        if (!res) {
            for (int i = 0; i < 4; ++i) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && !book[nx][ny] && board[nx][ny] == word[cur]) {
                    book[nx][ny] = 1;
                    if (dfs(nx, ny, cur + 1, board, word)) return true;
                    book[nx][ny] = 0;
                }
            }
        }
        return false;
    }

    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (board[i][j] == word[0]) {
                    book[i][j] = 1;
                    res = dfs(i, j, 1, board, word);
                    if (res) return true;
                    book[i][j] = 0;
                }
            }
        }
        return res;
    }
};

原题链接:https://leetcode-cn.com/problems/word-search/


3、全排列

题目描述

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题解

全排列的题目一般考虑的都是顺序,即:

  • 考虑当前位置放哪个数
  • 考虑当前数放哪个位置

看两张图理解一下

permutations1LeetCode.png

permutations2LeetCode.png

代码

class Solution {
public:

    int n;
    vector<bool> mark;
    vector<int> cur;
    vector<vector<int>> res;

    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        mark = vector<bool>(n, false);
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int>& nums, int u) {
        if (u == n) {
            res.push_back(cur);
            return;
        }

        for (int i = 0; i < n; ++i) {
            if (!mark[i]) {
                mark[i] = true;
                cur.push_back(nums[i]);
                dfs(nums, u + 1);
                cur.pop_back();
                mark[i] = false;
            }
        }
    }
};

原题链接:https://leetcode-cn.com/problems/permutations/

4、全排列 II

题目描述

给定一个可包含重复数字的序列 nums按任意顺序 返回所有不重复的全排列。

示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
 [1,2,1],
 [2,1,1]]
示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示:
  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

题解

这题和上一题差不多,只是多了一个条件:需要判重。

  • 首先对nums数组排个序,使所有相同数能够排在一起
  • 在搜索过程中加个去重就好了,若当前数和前一个数相同并且前一个数还未使用过,则跳过。

代码

class Solution {
public:

    int n;
    vector<bool> mark;
    vector<int> cur;
    vector<vector<int>> res;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        mark = vector<bool>(n, false);
        cur = vector<int>(n);

        sort(nums.begin(), nums.end());

        dfs(nums, 0);

        return res;
    }

    void dfs(vector<int>& nums, int u) {
        if (u == n) {
            res.push_back(cur);
            return;
        }

        for (int i = 0; i < n; ++i) {
            if (!mark[i]) {
                // 判重
                if (i > 0 && nums[i] == nums[i - 1] && !mark[i - 1]) continue;
                mark[i] = true;
                cur[u] = nums[i];
                dfs(nums, u + 1);
                mark[i] = false;
            }
        }
    }
};

原题链接:https://leetcode-cn.com/problems/permutations-ii/


5、子集

题目描述

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
提示:
  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

题解

方法一:位运算

序列中每个元素 ai 都有两种状态,选或者不选,即「在子集中」和「不在子集中」。用 1 表示「在子集中」,0 表示不在子集中,那么每一个子集可以对应一个长度为 n 的 0/1 序列,第 i 位表示 ai 。例如:序列 nums = {1,2,3} 时:

0/1序列子集对应的二进制数
000{}0
001{3}1
010{2}2
011{2,3}3
100{1}4
101{1,3}5
110{1,2}6
111{1,2,3}7
代码
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        for (int i = 0; i < (1 << n); ++i) {
            vector<int> t;
            for (int j = 0; j < n; ++j) {
                if (i & (1 << j)) t.push_back(nums[j]);
            }
            res.push_back(t);
        }
        return res;
    }
};
方法二:搜索

这种方法就不说了,直接上代码

class Solution {
public:

    vector<vector<int>> res;
    vector<int> st;

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int>& nums, int cur) {
        if (cur == nums.size()) {
            res.push_back(st);
            return;
        }

        st.push_back(nums[cur]);
        dfs(nums, cur + 1);

        st.pop_back();
        dfs(nums, cur + 1);
    }
};

原题链接: https://leetcode-cn.com/problems/subsets/

Q.E.D.