首页 > 编程语言 >【3.10】贪心算法-找出对应 LCP 矩阵的字符串

【3.10】贪心算法-找出对应 LCP 矩阵的字符串

时间:2024-09-01 17:21:47浏览次数:17  
标签:字符 word LCP lcp 3.10 字母 字符串 字典 贪心

一、题目

对任一由 n 个小写英文字母组成的字符串 word ,我们可以定义一个 n x n 的矩阵,并满足:

  • lcp[i][j] 等于子字符串 word[i,...,n-1]word[j,...,n-1] 之间的最长公共前缀的长度。

给你一个 n x n 的矩阵 lcp 。返回与 lcp 对应的、按字典序最小的字符串 word 。如果不存在这样的字符串,则返回空字符串。

对于长度相同的两个字符串 ab ,如果在 ab 不同的第一个位置,字符串 a 的字母在字母表中出现的顺序先于 b 中的对应字母,则认为字符串 a 按字典序比字符串 b 小。例如,"aabd" 在字典上小于 "aaca" ,因为二者不同的第一位置是第三个字母,而 'b' 先于 'c' 出现。

 

示例 1:

输入:lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
输出:"abab"
解释:lcp 对应由两个交替字母组成的任意 4 字母字符串,字典序最小的是 "abab" 。

示例 2:

输入:lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
输出:"aaaa"
解释:lcp 对应只有一个不同字母的任意 4 字母字符串,字典序最小的是 "aaaa" 。 

示例 3:

输入:lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]
输出:""
解释:lcp[3][3] 无法等于 3 ,因为 word[3,...,3] 仅由单个字母组成;因此,不存在答案。

 

提示:

  • 1 <= n == lcp.length == lcp[i].length <= 1000
  • 0 <= lcp[i][j] <= n

 

二、解题思路

        要解决这个问题,我们可以使用贪心算法的思路来逐步构建字符串 word。贪心算法的核心思想是在每一步选择中都采取当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的。

具体步骤如下:

  1. 初始化字符串:从第一个字符开始,逐步构建字符串 word

  2. 选择字符:对于每个位置 i,我们需要选择一个字符 word[i],使得它与之前的字符串 word[0:i] 和矩阵 lcp 中的信息一致,并且按字典序最小。

  3. 验证:选择字符后,验证它是否满足矩阵 lcp 中的信息。如果不满足,则返回空字符串。

  4. 迭代:继续选择下一个字符,直到构造完整个字符串。

具体的贪心策略如下:

  • 对于每个位置 i,我们尝试选择 az 中的每个字符,并检查它是否满足矩阵 lcp 中的信息。

  • 选择满足条件且按字典序最小的字符。

 

三、代码实现

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string findTheString(vector<vector<int>>& lcp) {
    int n = lcp.size();
    string word(n, ' ');

    for (int i = 0; i < n; ++i) {
        for (char c = 'a'; c <= 'z'; ++c) {
            word[i] = c;
            bool valid = true;
            for (int j = 0; j <= i; ++j) {
                int prefix_len = 0;
                while (i + prefix_len < n && j + prefix_len < n && word[i + prefix_len] == word[j + prefix_len]) {
                    ++prefix_len;
                }
                if (lcp[i][j] != prefix_len || lcp[i][j] != lcp[j][i]) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                break;
            }
        }
        if (!valid) {
            return "";
        }
    }

    return word;
}

int main() {
    vector<vector<int>> lcp1 = {{4, 0, 2, 0}, {0, 3, 0, 1}, {2, 0, 2, 0}, {0, 1, 0, 1}};
    cout << findTheString(lcp1) << endl;  // 输出: "abab"

    return 0;
}

 

 

标签:字符,word,LCP,lcp,3.10,字母,字符串,字典,贪心
From: https://blog.csdn.net/linshantang/article/details/141753556

相关文章

  • 分享丨【题单】贪心算法(基本贪心策略/反悔/区间/字典序/数学/思维/构造)
    作者:灵茶山艾府链接:https://leetcode.cn/circle/discuss/g6KTKL/一、贪心策略有两种基本贪心策略:从最小/最大开始贪心,优先考虑最小/最大的数,从小到大/从大到小贪心。在此基础上,衍生出了反悔贪心。从最左/最右开始贪心,思考第一个数/最后一个数的贪心策略,把n个数的原问题转......
  • 【3.4】贪心算法-解按要求补齐数组
    一、问题        给定一个已排序的正整数数组nums,和一个正整数n。从[1,n]区间内选取任意个数字补充到nums中,使得[1,n]区间内的任何数字都可以用nums中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。......
  • CentOS 7.9 内核从 3.10 升级到 5.4
    1.背景介绍环境需求:在搭建Kubernetes(K8S)环境时,内核版本最好大于4.4以支持K8S的所有特性。当前内核版本:CentOS7.9的默认内核版本为3.10.0-1160.el7.x86_64,不满足K8S的推荐内核版本要求。2.查看内核版本及相关包使用命令uname-r查看当前内核版本。使用命令r......
  • Luogu P4425 转盘 题解 [ 黑 ] [ 线段树 ] [ 贪心 ] [ 递归 ]
    转盘:蒟蒻的第一道黑,这题是贪心和线段树递归合并的综合题。贪心破环成链的trick自然不用多说。首先观察题目,很容易发现一个性质:只走一圈的方案一定最优。这个很容易证,因为再绕一圈回来标记前面的和等前面的标记完之后继续走是等价的,并且再绕一圈甚至可能更劣。于是,我们只用走......
  • 代码随想录算法训练营第二十九天(贪心 三)
    力扣题部分:134.加油站题目链接:.-力扣(LeetCode)题面:在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为......
  • 力扣热题100_贪心算法_45_跳跃游戏
    文章目录题目链接解题思路解题代码题目链接45.跳跃游戏II给定一个长度为n的0索引整数数组nums。初始位置为nums[0]。每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说,如果你在nums[i]处,你可以跳转到任意nums[i+j]处:0<=j<=nums[i]......
  • 代码随想录算法day24 | 贪心算法part02 | 122.买卖股票的最佳时机II,55. 跳跃游戏,45.跳
    122.买卖股票的最佳时机II本题解法很巧妙,本题大家可以先自己思考一下然后再看题解,会有惊喜!力扣题目链接(opensnewwindow)给定一个数组,它的第 i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次......
  • 牛客周赛 Round 57 D-小红的线段(贪心)
     示例1输入2-1200011011输出112N34Y说明连接第一个点和第二个点,和直线没有交点。连接第三个点和第四个点,和直线有交点。 贪心策略:把点集分为三部分,直线上方m1、直线下方m2以及在直线上m3,我们可以发现:m1中的点和m2中的任意点相连都能通过直线;m3......
  • 题解:SP3109 STRLCP - Longest Common Prefix
    三倍经验:UVA11996JewelMagicP4036[JSOI2008]火星人题意维护一个字符串\(S\),支持以下操作:\(Q\i\j\):输出\(\operatorname{LCP}(S[i\dotsl],S[j\dotsl])\)\(R\i\char\):用\(char\)替换\(S\)的第\(i\)个字符\(I\i\char\):在\(S\)的第\(i\)......
  • 贪心模型
    邻项交换模型邻项交换十分的重要,因为他是一个不可替代的算法。需要知道什么时候使用邻项交换,没有固定的形态,需要通过做题形成一种经验。P1080国王游戏题目描述有\(n\)个人,每一个人左手写了\(a_i\),右手写了\(b_i\)。需要确定一个\(1,2,\dots,n\)的排列\(p\),使得最......