C++ 中输入给定字符串所需的最小按键次数

2024 年 8 月 29 日 | 阅读 12 分钟

引言

你可以使用动态规划来找出在 C++ 中输入给定字符串所需的最小按键次数。思路是构建一个表，其中每个条目dp[i][j]表示输入子串 s[i..j]所需的最小按键次数。该表以自底向上的方式填充。

程序

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int minKeypresses(const string& s) {
    int n = s.length();
    // Create a 2D DP table to store the results
    vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
    // Initialize the diagonal elements where the substring has length 1
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }
    // Iterate over all possible substring lengths
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            // Check if the substring is a palindrome
            if (s[i] == s[j] && len == 2) {
                dp[i][j] = 1;
            } else if (s[i] == s[j]) {
                // If the endpoints are the same, the result is the same as for the substring without the endpoints
                dp[i][j] = dp[i + 1][j - 1];
            }
            // Try all possible partitions and update the result
            for (int k = i; k < j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
            }
        }
    }
    // The result is stored in the top-right corner of the table
    return dp[0][n - 1];
}
int main() {
    string s;
    cout << "Enter the string: ";
    cin >> s;
    int result = minKeypresses(s);
    cout << "Minimum number of keypresses: " << result << endl;
    return 0;
}

输出

Enter the string: abcdefghij
Minimum number of keypresses: 10

说明

初始化

在此示例中，代码首先包含必要的库，例如 stream 和 vector。

定义了minKeypresses 函数来计算输入给定字符串所需的最小按键次数。

创建了一个名为 dp 的二维向量来存储结果。dp[i][j]将表示从索引 i 到 j 的子串所需的最小按键次数。

该函数以字符串作为输入

动态规划表

dp 表的对角线元素初始化为 1。这是因为长度为 1 的子串只需要一次按键。

然后，该函数遍历所有可能的子串长度（2 或更长），并考虑给定字符串内的所有可能的子串。

回文检查

对于每个子串，它会检查端点是否相同（即子串是否为回文）。如果是，则按键次数设置为1。

如果端点相同，则结果与不包含这些端点的子串相同。

分割

代码然后尝试子串内的不同分割点，并相应地更新最小按键次数。

它检查所有可能的分割，并跟踪所需的最小按键次数。

结果

最终结果存储在dp[0][n - 1]中，其中 n 是输入字符串的长度。它表示整个字符串所需的最小按键次数。

主函数

main 函数接收用户输入的字符串。

它使用输入的字符串调用minKeypresses函数，并打印结果。

复杂度分析

时间复杂度

代码使用自底向上的动态规划方法来填充 dp 表。

两个嵌套循环遍历字符串中所有可能的子串长度和位置。

第三个循环遍历可能的分割点。

因此，时间复杂度为 O(n^3)，其中“n”是输入字符串的长度。

空间复杂度

二维向量 dp 决定了空间复杂度。

dp 表的大小为n x n，其中“n”是输入字符串的长度。

因此，空间复杂度为O(n^2)，因为它取决于输入大小的平方。

方法 1：使用贪心算法

遍历字符串并计算连续字符的数量。

如果一个字符连续重复，你可以考虑在一次按键中输入该字符及其重复的次数。

程序

#include <iostream>
using namespace std;
int minKeypressesGreedy(const string& s) {
    int n = s.length();
    // Edge case: empty string
    if (n == 0) {
        return 0;
    }
    int totalKeypresses = 1; // Start with 1 to account for the first character
    // Iterate through the string to count consecutive characters
    for (int i = 1; i < n; ++i) {
        int count = 1; // Count of consecutive characters
        while (i < n && s[i] == s[i - 1]) {
            ++count;
            ++i;
        }
        // Add the character and its count to the total keypresses
        totalKeypresses += 1 + (count > 1 ? 1 : 0); // Typing the character and its count
        // Note: If count is 1, no extra keypress is needed for the count
    }
    return totalKeypresses;
}
int main() {
    string s;
    cout << "Enter the string: ";
    cin >> s;
    int result = minKeypressesGreedy(s);
    cout << "Minimum number of keypresses: " << result << endl;
    return 0;
}

输出

Enter the string: JavaTpoint
Minimum number of keypresses: 10

说明

输入

接收一个字符串 s 作为输入。

边界情况

检查字符串是否为空。如果是，则函数返回 0，因为没有字符可以输入。

初始化

将 totalKeypresses 初始化为1。这是为字符串中的第一个字符准备的。

遍历字符串

使用循环遍历字符串中的每个字符。

对于每个字符，它使用 while 循环计算有多少连续字符相同。

在计数时，它移动到下一个字符，直到遇到不同的字符。

计算按键次数

将连续字符的数量加上输入字符本身所需的额外 1 加到totalKeypresses中。

如果计数为1（即，没有连续重复的字符），则不为计数添加额外的按键次数。

结果

它返回 totalKeypresses 的最终值，表示输入给定字符串所需的最小按键次数。

主函数

输入

它接收用户输入的字符串。

函数调用

使用输入的字符串调用minKeypressesGreedy函数。

打印结果

打印从函数获得的最小按键次数。

复杂度分析

时间复杂度

遍历字符串

for 循环遍历字符串中的每个字符一次。

其中的 while 循环计算连续字符的数量。

在最坏的情况下，每个字符可能会被访问两次（一次在外部循环中，一次在 while 循环中）。

因此，遍历的时间复杂度为O(n)，其中“n”是输入字符串的长度。

计算按键次数

循环内的计算每个字符需要恒定的时间。

整体时间复杂度仍为O(n)。

主函数

main 函数接收输入并调用时间复杂度为O(n)的minKeypressesGreedy函数。

代码的整体时间复杂度为O(n)。

空间复杂度

附加变量

代码使用的额外空间量与输入大小无关。

诸如totalKeypresses、count和循环变量之类的变量不依赖于输入大小。

空间复杂度为 O(1)，表示恒定的空间使用。

方法 2：使用 Manacher 算法查找最长回文子串

查找给定字符串中最长回文子串。

剩余字符串的长度减去回文子串的长度即为所需的最小按键次数。

程序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to preprocess the string and insert '#' between characters
string preprocess(const string& s) {
    string result = "#";
    for (char c : s) {
        result += c;
        result += '#';
    }
    return result;
}
// Manacher's Algorithm to find the length of the longest palindromic substring
int longestPalindromicSubstring(const string& s) {
    string processedString = preprocess(s);
    int n = processedString.length();
    // Create an array to store the lengths of palindromes centered at each index
    vector<int> palindromeLengths(n, 0);
    int center = 0; // Center of the rightmost palindrome
    int right = 0;  // Right boundary of the rightmost palindrome
    for (int i = 0; i < n; ++i) {
        // Reflect the index 'i' around the center
        int mirror = 2 * center - i;
        // Check if 'i' is within the right boundary
        if (i < right) {
            palindromeLengths[i] = min(right - i, palindromeLengths[mirror]);
        }
        // Attempt to expand the palindrome centered at 'i'
        int a = i + (1 + palindromeLengths[i]);
        int b = i - (1 + palindromeLengths[i]);
        while (a < n && b >= 0 && processedString[a] == processedString[b]) {
            ++palindromeLengths[i];
            ++a;
            --b;
        }
        // Update the right boundary and center if needed
        if (i + palindromeLengths[i] > right) {
            center = i;
            right = i + palindromeLengths[i];
        }
    }
    // Find the maximum length in the palindromeLengths array
    int maxPalindromeLength = *max_element(palindromeLengths.begin(), palindromeLengths.end());
    return maxPalindromeLength;
}
// Function to calculate the minimum keypresses using Manacher's algorithm
int minKeypressesManacher(const string& s) {
    int longestPalindromeLength = longestPalindromicSubstring(s);
    int remainingLength = s.length() - longestPalindromeLength;
    // Subtract the length of the longest palindromic substring from the total length
    return remainingLength;
}
int main() {
    string inputString;
    cout << "Enter the string: ";
    cin >> inputString;
    int result = minKeypressesManacher(inputString);
    cout << "Minimum number of keypresses: " << result << endl;
    return 0;
}

输出

Enter the string: abcde
Minimum number of keypresses: 4

说明

预处理函数 (preprocess)

输入

它接收一个字符串 s 作为输入。

过程

在字符串中的每个字符之间插入'#'。这样做是为了有效地处理偶数和奇数长度的回文。

Manacher 算法函数 (longestPalindromicSubstring)

输入

接收预处理后的字符串作为输入。

初始化

初始化变量以表示迄今为止找到的最右回文的中心和右边界。

回文长度数组

创建一个数组来存储以每个索引为中心的那些回文的长度。

算法执行

遍历预处理字符串中的每个字符。

利用对称性来避免不必要的比较，并有效地找到以每个索引为中心的那些回文的长度。

更新中心和右边界

根据找到的回文更新中心和右边界。

查找最大长度

在回文长度数组中查找最大长度。

结果

返回最长回文子串的长度。

最小按键次数计算函数 (minKeypressesManacher)

输入

接收原始字符串作为输入。

最长回文子串长度

调用longestPalindromicSubstring函数查找最长回文子串的长度。

计算最小按键次数

通过从原始字符串的总长度中减去最长回文子串的长度来计算最小按键次数。

结果

返回最小按键次数。

主函数

输入

接收用户输入的原始字符串。

函数调用

使用输入的字符串调用minKeypressesManacher函数。

打印结果

它打印从函数获得的最小按键次数。

复杂度分析

时间复杂度

预处理函数 (preprocess)

遍历原始字符串中的每个字符一次，在字符之间插入'#'。

此函数的复杂度为O(n)，其中“n”是原始字符串的长度。

Manacher 算法函数 (longestPalindromicSubstring)

它遍历预处理后的字符串中的每个字符一次。

Manacher 算法的时间复杂度为O(n)，其中“n”是预处理字符串的长度。

最小按键次数计算函数 (minKeypressesManacher)

它调用了复杂度为O(n)的longestPalindromicSubstring函数。

执行简单的算术运算，这些运算需要恒定的时间。

代码的整体时间复杂度为O(n)。

空间复杂度

预处理函数 (preprocess)

创建一个长度为 2n 的新字符串（原始字符串中的每个字符加上插入的 '#'）。

此函数的空间复杂度为O(n)。

Manacher 算法函数 (longestPalindromicSubstring)

为长度为 n 的回文长度数组使用额外的空间。

Manacher 算法的空间复杂度为O(n)。

最小按键次数计算函数 (minKeypressesManacher)

它为变量使用恒定的空间。

空间复杂度为O(1)。

代码的整体空间复杂度为 O(n)。

方法 3：使用计数唯一字符

计算字符串中唯一字符的数量。

最小按键次数将是字符串长度减去唯一字符的数量。

程序

#include <iostream>
#include <unordered_set>
using namespace std;
int minKeypressesCountUnique(const string& s) {
    int n = s.length();
    // Use an unordered_set to keep track of unique characters
    unordered_set<char> uniqueCharacters;
    // Traverse the string and insert each character into the set
    for (char c : s) {
        uniqueCharacters.insert(c);
    }
    // Calculate the minimum keypresses using the formula
    int minKeypresses = n - uniqueCharacters.size();
    return minKeypresses;
}
int main() {
    string inputString;
    cout << "Enter the string: ";
    cin >> inputString;
    int result = minKeypressesCountUnique(inputString);
    cout << "Minimum number of keypresses (Count Unique Characters): " << result << endl;
    return 0;
}

输出

Enter the string: jtp
Minimum number of keypresses: 0

说明

输入

minKeypressesCountUnique函数以字符串作为输入。

唯一字符的集合

初始化一个无序集合（uniqueCharacters）来跟踪遇到的唯一字符。

遍历并插入

它遍历字符串中的每个字符并将其插入到集合中。集合会自动确保唯一性。

最小按键次数计算

它使用以下公式计算最小按键次数：字符串长度 - 唯一字符的数量。

结果

将最小按键次数作为结果返回。

复杂度分析

时间复杂度

遍历并插入（minKeypressesCountUnique 函数）

遍历字符串中的每个字符一次，并将其插入到无序集合中。

此操作的时间复杂度为O(n)，其中“n”是输入字符串的长度。

计算最小按键次数

计算最小按键次数涉及查找无序集合的大小。

查找无序集合大小的时间复杂度平均为O(1)。

代码的整体时间复杂度为 O(n)。

空间复杂度

唯一字符的空间（无序集合）

空间复杂度受无序集合的影响，该集合存储唯一字符。

在最坏的情况下，所需的空间为O(min(n, m))，其中“n”是输入字符串的长度，“m”是唯一字符的数量。

附加空间

除了无序集合外，代码还为 n、result 和循环变量等变量使用了恒定的额外空间。

整体空间复杂度为O(min(n, m))，其中“n”是输入字符串的长度，“m”是唯一字符的数量。

方法 4：使用分治法

“分治法”方法包括将问题分解为更小的片段，递归地解决每个片段，然后合并结果以获得整个问题的解决方案。在查找给定字符串的最小按键次数的上下文中，我们可以通过将字符串划分为更小的部分，计算每个部分的按键次数，然后合并结果来应用此方法。

程序

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// Function to calculate minimum keypresses for a segment of the string
int minKeypressesSegment(const string& segment) {
    // Simple example: just return the length of the segment
    // You can implement more complex logic based on segment characteristics
    return segment.length();
}
// Function to calculate minimum keypresses using Divide and Conquer
int minKeypressesDivideConquer(const string& s, int start, int end) {
    // Base case: if the segment has only one character
    if (start == end) {
        return 1; // Typing a single character requires one key press
    }
    // Divide the segment into two halves
    int mid = start + (end - start) / 2;
    // Recursively calculate minimum keypresses for each half
    int leftKeypresses = minKeypressesDivideConquer(s, start, mid);
    int rightKeypresses = minKeypressesDivideConquer(s, mid + 1, end);
    // Combine the results based on the characteristics of the segments
    // For simplicity, we add the keypresses for each half in this example
    int combinedKeypresses = leftKeypresses + rightKeypresses;
    return combinedKeypresses;
}
int main() {
    string inputString;
    cout << "Enter the string: ";
    cin >> inputString;
    int result = minKeypressesDivideConquer(inputString, 0, inputString.length() - 1);
    cout << "Minimum number of keypresses: " << result << endl;
    return 0;
}

输出

Enter the string: world
Minimum number of keypresses: 5

说明

minKeypressesSegment 函数

代表一个计算给定片段最小按键次数的函数。此函数可以根据片段的特征进行自定义。

minKeypressesDivideConquer 函数

它接收输入字符串 s 和索引 start 和 end 来定义片段。

基本情况：如果片段只有一个字符，则返回 1，因为输入单个字符需要一次按键。

将片段划分为两半（start 到 mid 和mid+1 到 end）。

递归计算每半部分的最小按键次数。

根据片段的特征合并结果。在此示例中，我们将每半部分的按键次数相加。

返回合并后的结果。

主函数

接收用户输入的原始字符串。

使用整个字符串调用minKeypressesDivideConquer函数。

复杂度分析

时间复杂度

递归调用（minKeypressesDivideConquer 函数）

在每次递归调用中，该函数将片段划分为两半。

递归调用的数量与递归树的深度成正比，而递归树的深度与输入字符串的长度呈对数关系。

递归树的每个级别需要O(1)的时间来合并结果和处理基本情况。

整体时间复杂度为O(log n)，其中“n”是输入字符串的长度。

minKeypressesSegment 函数（自定义逻辑）

此函数的复杂度取决于用于计算片段按键次数的自定义逻辑。

在提供的示例中，它仅返回片段的长度，这需要O(1)时间。

如果实现了更复杂的逻辑，复杂度可能会有所不同。

递归调用是整体复杂度的主要因素，复杂度为O(log n)。

空间复杂度

堆栈空间（minKeypressesDivideConquer 函数）

空间复杂度由递归堆栈的最大深度决定。

在最坏的情况下，最大深度与输入字符串的长度呈对数关系。

因此，由于递归导致的复杂度为O(log n)。

附加变量

代码为 mid、leftKeypresses、rightKeypresses以及循环变量等变量使用了恒定的额外空间。

整体空间复杂度为O(1)，表示恒定的空间使用。

下一主题C++ 中的范围按位与所有子数组之和的查询

← 上一个下一个 →

C++ 中输入给定字符串所需的最小按键次数

引言

程序

方法 1：使用贪心算法

程序

方法 2：使用 Manacher 算法查找最长回文子串

程序

方法 3：使用计数唯一字符

程序

方法 4：使用分治法

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中输入给定字符串所需的最小按键次数

引言

程序

方法 1：使用贪心算法

程序

方法 2：使用 Manacher 算法查找最长回文子串

程序

方法 3：使用计数唯一字符

程序

方法 4：使用分治法

程序

相关帖子

C++ Long 数据类型

C++ fma() 函数

C++ 食堂管理系统

C++ STL 中的数组求和

C++ 程序执行 Baillie-PSW 素数测试

C++ 不使用第三方变量交换两个数字的程序

C/C++ mbsrtowcs() 函数

不透明指针

使用栈数据结构将中缀表达式转换为后缀表达式的 C++ 程序

C++ 中 list::emplace_front() 和 list::emplace_back() 的区别