0

我需要找到两个相似字符串之间的最大字母数。例如考虑以下字符串：

progxrammerrxproxgrammer

我需要找到first和 secondrx之间的 2 长度。为了实现这一点，我需要找到一种方法来识别上述字符串的子集，可以重新排列以形成单词“programmer”。作为另一个例子，考虑一下：progxrammerproxgrammer

xprogxrmaxemrppprmmograeiruu

它应该再次找到pp在两组programmer单词之间的。

我尝试了以下方法，但我真的不知道如何实现这一目标？

public static int programmerStrings(string s)
{
    var firstPart = s.ToLower().Contains("programmer");

    var secondPart = s.ToLower().Contains("programmer");

    return (secondPart - firstPart).Length;
}
4

3 回答 3

2

基本上，您需要从头开始搜索字符，然后再从尾开始搜索，以找到位于相似“单词”之间的字符串的开头和结尾。以下将获取该字符串的长度，如果不存在则为 -1。

public int LengthBetween(string word, string input)
{
    int start = 0;
    int end = input.Length - 1;
    var letters = word.ToList();
    while(start < input.Length && letters.Count > 0)    
    {
        letters.Remove(input[start]);
        start++;
    }

    letters = word.ToList();
    while(end >= 0 && letters.Count > 0)    
    {
        letters.Remove(input[end]);
        end--;
    }

    if(start > end) return -1;
    return end - start + 1;
}

然后打电话

LengthBetween("programmer", "progxrammerrxproxgrammer")

将返回 2。

相反，如果您需要实际单词，只需将返回类型string更改为并将结尾更改为

if(start > end) return null;
return input.Substring(start, end - start + 1);
于 2020-03-03T14:43:21.943 回答
0

正则表达式怎么样？

public int LengthBetween(string word, string input)
{
    var pattern = "p[^r]*r[^o]*o[^g]*g[^r]*r[^a]*a[^m]*m[^m]*m[^e]*e[^r]*r(.*)p[^r]*r[^o]*o[^g]*g[^r]*r[^a]*a[^m]*m[^m]*m[^e]*e[^r]*r";
    var match = Regex.Match(input, pattern);
    return match.Success ? match.Groups[1].Value.Length : -1;
}

这将适用于progxrammer rx proxgrammer女巫有额外的字母。但如果这应该适用，xprogxrmaxemr pp prmmograeiruu我会找莱文斯坦检查相似度。

于 2021-07-15T21:11:09.330 回答
0

这是我的 C++ 方法。

主意

  • 如果给定字符串的长度小于目标字符串，则 NO ANSWER 或 -1
  • 否则，请执行以下操作：
    • 创建一个映射（假设是目标计数器）来存储目标字符串中所有字符的计数。
    • 看，由于目标字符串大小是固定的，我们只需要寻找|given string size| - |target size| + 1窗口。
    • 使用 while 循环遍历所有窗口，并为每个窗口创建一个计数器 (tmp Counter) 来存储所有计数。
    • 然后，遍历目标字符串并使用目标计数器和tmp 计数器来验证当前是否有效。
    • 如果有效则存储当前窗口的索引。这有助于计算距离。
  • 然后，一旦我们完成了，那么对于不同的情况，我们将返回适当的结果。
    • 如果没有有效的窗口，我们将返回 -1
    • 如果只有一个窗口有效，那么我们将返回 0，因为该窗口与自身的距离为 0
    • 如果我们有超过 1 个窗口，则在数组中（存储所有索引的位置）使用第一个和最后一个值返回结果。对于上述情况，结果将是最右边有效窗口开始到最左边有效窗口结束之间的差异。
#include<iostream>
#include<map>
#include<vector>
#include<string>

using namespace std;

int solve(string s, string t){
    
    if(s.size() < t.size()) return -1;
    map<char, int> tm;
    for(auto i : t) tm[i]++;
    
    
    int l = s.size(), g = t.size(), i = 0;
    
    vector<int> v;
    
    while(i < l-g+1)
    {   bool flag = true;
        map<char, int> tmpMap;
        for(int j = i; j<i+g; j++)
        {
            tmpMap[s[j]]++;
        }
        
        for(auto k: t){
            if(tm[k] != tmpMap[k])
            {
                flag = false;
                break;
            }
        }
        
        if(flag) v.push_back(i);
        i++;
    }
    
    
    if(v.size() == 0) return -1;
    if(v.size() == 1) return 0;
    // Ending of leftmost to starting of rightmost
    return v[v.size()-1] - v[0] - g;
}


int main(){
    int tcs;
    cin>>tcs;
    while(tcs--){
        string s, t;
        cin>>s>>t;
        cout<<solve(s, t)<<endl;
    }
}
于 2021-07-15T20:22:38.837 回答