[LeetCode 双周赛24] 3. 长度为 n 的开心字符串中字典序第 k 小的字符串(暴力、状态压缩、巧妙解法)

文章目录

• • 1. 题目来源
  • 2. 题目说明
  • 3. 题目解析
  • • 方法一：暴力+状态压缩+巧妙解法
    • 方法二：dfs+常规解法

1. 题目来源

链接：5374. 长度为 n 的开心字符串中字典序第 k 小的字符串

2. 题目说明

3. 题目解析

方法一：暴力+状态压缩+巧妙解法

由于排序规则给定，第一感觉可以通过寻找规律直接进行构造性输出。但思索了一阵，还是暴力更得我心。下面来看一种模拟全排列 + 状态压缩的一种暴力方法：

• 由于

  k

  的数据范围很小，所以可以暴力解决，即先生成全排列，由于全排列一定是按照字典序进行输出的，并且需要将不满足 快乐，定义的全排列的字符串进行剔除
• 下面来看看状态压缩：由于只有，

  'a'、'b'、'c'

  ，这三种情况，那么就可以用三进制来进行状态压缩，也就是暴力，每一位都会产生三种情况，那么

  n

  位即会产生 3 n 3^n 3n 种情况，可以首先得到所有的状态情况
• 由于是三进制，我们可以通过模三再除三的形式，得到最后一位填的是什么颜色。如果不好理解的话，建议通过

  n = 2

  的 9 种状态情况进行理解，举例子模拟下就能理解到其中含义了，这个一定得自己动手动笔的
• 若遍历所有位均不相同，则该状态为一个开心字符串，

  ++cnt

  计数，如果

  cnt

  刚好等于

  k

  了，那么就将这个状态转化为字符串即可

状态压缩真的是一种很厉害的方法，很抽象，但效率很高。希望能够多多理解吧，状压，数位真的厉害的。

参见代码如下：

// 执行用时 :4 ms, 在所有 C++ 提交中击败了100.00%的用户
// 内存消耗 :5.9 MB, 在所有 C++ 提交中击败了100.00%的用户

class Solution {
public:
    string getHappyString(int n, int k) {
        int lim = 1, cnt = 0;
        for (int i = 0; i < n; ++i) lim *= 3;

        for (int i = 0; i < lim; ++i) {
            bool flag = true;
            for (int j = 1, k = i, last = 3; j <= n and flag; ++j) {
                int cur = k % 3; k /= 3;
                cout << cur << endl;
                if (last == cur) flag = false;
                last = cur;
            }
            if (flag) ++cnt;

            if (cnt == k) {
                string ans = "";
                for (int m = 1, v = i; m <= n; ++m) {
                    int cur = v % 3; v /= 3;
                    ans = (char)('a' + cur) + ans;
                }
                return ans;
            }
        }
        return "";
    }
};
           

方法二：dfs+常规解法

依旧模拟全排列，判断相邻不重复即可。

dfs

解法确实更加清楚点。

参见代码如下：

// 执行用时 :4 ms, 在所有 C++ 提交中击败了100.00%的用户
// 内存消耗 :5.9 MB, 在所有 C++ 提交中击败了100.00%的用户

class Solution {
public:
    string s, ans;
    int cnt = 0;
    string getHappyString(int n, int k) {
        dfs(n, k);
        return cnt == k ? ans : "";
    }
    void dfs(int n, int k) {
        if (cnt == k) return;

        if (s.size() == n) {
            ++cnt;
            ans = s;
            return;
        }
        
        for (int c = 'a'; c <= 'c'; ++c) {
            if (s.size() && s.back() == c) continue;
            s.push_back(c);
            dfs(n, k);
            s.pop_back();
        }
    }
};