太原理工大学2025数据结构实验四-字符串

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

第1关：最长公共前缀

#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

string longestCommonPrefix(string * strs, int strsSize)
{
    //strs为字符串数组，由strsSize个string类字符串组成
    //在此处写入代码，以string类返回最长的公共前缀
    string s;
    int len=0x3f3f3f3f;
    for(int i=0;i<strsSize;i++)
    {
        len=min(len,(int)strs[i].size());
    }
    for(int i=0;i<len;i++)
    {
        // if(flag)return s;
        // flag=0;
        char ch=strs[0][i];
        for(int j=1;j<strsSize;j++)
        {
            if(ch!=strs[j][i])return s;
        }
        s+=ch;
    }
    return s;
}
// string longestCommonPrefix(string* strs, int strsSize) {
//     // 1. 处理空数组或首个字符串为空的情况（直接返回空前缀）
//     if (strsSize == 0 || strs[0].empty()) {
//         return "";
//     }

//     string commonPrefix; // 存储最终的公共前缀
//     // 2. 外层循环：遍历第一个字符串的每一位（作为前缀的候选位）
//     for (int i = 0; i < strs[0].size(); i++) {
//         char currentChar = strs[0][i]; // 取第一个字符串的第i个字符作为基准
        
//         // 3. 内层循环：对比其他所有字符串的第i个字符
//         for (int j = 1; j < strsSize; j++) {
//             // 两种终止情况：
//             // a. 某字符串的长度已不足i位（当前i超出其范围）
//             // b. 当前字符串的第i个字符与基准字符不匹配
//             if (i >= strs[j].size() || strs[j][i] != currentChar) {
//                 return commonPrefix; // 直接返回已积累的前缀
//             }
//         }
        
//         // 4. 所有字符串的第i位均匹配，将当前字符加入公共前缀
//         commonPrefix += currentChar;
//     }

//     // 5. 所有字符串完全匹配（第一个字符串就是公共前缀）
//     return commonPrefix;
// }

第2关：反转字符串中的单词

#include <iostream>
#include <cstdlib>
#include <string>
#include<algorithm>
using namespace std;

string reverseWords(string s)
{
    //在此处写入代码
    reverse(s.begin(),s.end());
    int left = 0; int right = 0;
    while (right < s.size())
    {
        while (right < s.size() && s[right] != ' ')right++;
        reverse(s.begin() + left, s.begin() + right); 
        while (right < s.size() && s[right] == ' ')right++;
        left = right; 
    }
    string ret;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]==' '&&s[i-1]==' ')continue;
        ret+=s[i];
    }
    return ret;
}

第3关：最短编辑距离

#include <iostream>
#include <cstdlib>
#include<vector>
#include <string>
using namespace std;
//可进行空间优化，懒得写了
int minDistance(string word1, string word2) {
    int m = word1.size(); // word1的长度
    int n = word2.size(); // word2的长度

    // 定义(m+1)行、(n+1)列的DP数组，初始值为0
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 初始化第一行（word1为空的情况）
    for (int j = 0; j <= n; ++j) {
        dp[0][j] = j;
    }
    // 初始化第一列（word2为空的情况）
    for (int i = 0; i <= m; ++i) {
        dp[i][0] = i;
    }

    // 填充DP数组
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i-1] == word2[j-1]) {
                // 字符相等，无需操作
                dp[i][j] = dp[i-1][j-1];
            } else {
                // 字符不相等，取三种操作的最小值+1
                dp[i][j] = min( min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1] ) + 1;
            }
        }
    }

    // dp[m][n]即为word1转word2的最少操作数
    return dp[m][n];
}

第4关：坏掉的键盘

#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

bool isLongPressedStr(string origin,string typed)
{
    //origin为原始字符串，typed为键盘键入的字符串
    //在此处写入代码
    int cnt=0;
    for(int i=0;i<origin.size();i++)
    {
        if(origin[i]==typed[cnt])cnt++;
        else
        {
            while(typed[cnt]==origin[i-1])cnt++;
            if(origin[i]==typed[cnt])cnt++;
            else return false;
        }
    }
    while(typed[cnt]==origin[origin.size()-1])cnt++;
    if(cnt<typed.size()&&typed[cnt]!=origin[origin.size()-1])return false;
    return true;
}

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：太原理工 数据结构 理工大学 理工大 字符串