【Leetcode】466. 统计重复个数

2024-01-03 06:05:59

文章目录

题目

466. 统计重复个数
在这里插入图片描述

思路

题目要求找出一个最大整数 m,使得经过 n2 个字符串 s2 组成的字符串能够被经过 n1 个字符串 s1 组成的字符串完全包含的次数。使用动态规划来记录每个位置匹配的情况,并通过循环节的分析来计算最终的匹配次数。

代码

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int len1 = s1.length();
        int len2 = s2.length();
        vector<vector<int>> next(len1 + 1, vector<int>(26, 0));
        vector<vector<int>> dp(len1 + 1, vector<int>(2, 0));

        for (int i = 0; i < 26; i++) {
            next[len1][i] = INT_MAX;
        }

        for (int i = len1 - 1; i >= 0; i--) {
            int idx = s1[i] - 'a';
            for (int j = 0; j < 26; j++) {
                next[i][j] = next[i + 1][j];
                if (j == idx) {
                    next[i][j] = i + 1;
                }
            }
        }

        for (int i = 0; i < len1 + 1; i++) {
            int count = 0;
            int offset = i;

            int j = 0;
            while (j < len2) {
                int idx = s2[j] - 'a';
                int pos = next[offset][idx];

                if (offset == 0 && pos == INT_MAX) {
                    return 0;
                }
                if (pos == INT_MAX) {
                    offset = 0;
                    count++;
                } else {
                    offset = pos;
                    j++;
                }
            }
            dp[i][0] = count;
            dp[i][1] = offset;
        }

        int p = 1;
        int total = 0;
        int offset = 0;
        while (p <= n1) {
            int count = dp[offset][0];
            int idx = dp[offset][1];
            if (p + count > n1) {
                break;
            }

            p = p + count;
            total++;
            offset = idx;
        }

        return total / n2;
    }
};

文章来源:https://blog.csdn.net/m0_67724631/article/details/135352426
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。