两个字符串相互查询,并且找出相同的内容

@zgcwkj  2021年01月11日

分类:

代码 其它 

两个字符串相互查询,并且找出相同的内容,时间复杂度非 O(n*n),C# 实例

以下内容为代码,具体问题需具体解决

List<string> sameStr = new List<string>();
string strA = "主题是文章中通过具体材料所表达的基本思想";
string strB = "题是主文章中通过具体材的基本思想料所表达";
List<string> charStrA = strA.ToList().Select(T => T.ToString()).ToList();
List<string> charStrB = strB.ToList().Select(T => T.ToString()).ToList();
int ok = 0, startAIndex = 0, startBIndex = 0, endMark = 0;
foreach (var chara in charStrA)
{
    int listAIndex = charStrA.IndexOf(chara);
    int listBIndex = charStrB.IndexOf(chara);
    if (ok == 1)
    {
        //找到没有
        if (listBIndex != -1)
        {
            //B是否连续
            if (endMark == listBIndex - 1)
            {
                endMark = listBIndex;
                goto gotoExit;
            }
        }
        //输出结果
        string sameA = strA.Substring(startAIndex, listAIndex - startAIndex);
        string sameB = strB.Substring(startAIndex, listAIndex - startAIndex);
        if (sameA == sameB)//两者完全相同的索引时
        {

        }
        if (sameA.Length > 1)//两个以上相同的字符
        {
            sameStr.Add(sameA);
        }
        ok = 0;
        endMark = listBIndex;
    }
gotoExit:
    //防止丢失
    if (listBIndex != -1 && ok == 0)
    {
        ok = 1;
        startAIndex = listAIndex;
        startBIndex = listBIndex;
    }
}

水平有限仅供参考,如果有更好的建议,扔出来!!!



添加新评论

  1. 前段时间过来逛了一下,发现比较前面的文章都评论不了

    C# 不会,只能看个大概意思,看到 goto 比较方,哈哈。。

    题目的意思不是太明白,是想判断字符串内容完全相同(不需要管顺序)?

    是这个意思的话,我的方法是:分别遍历两个字符串成两个 map,然后再一次循环比较两个 map (key 是一个字符,value 是这个字符出现的次数)
    时间复杂度:O(3n) 忽略常数,即为 O(n)
    空间复杂度:O(2n) 忽略常数,即为 O(n)

    回复
    1. @LukaChen

      1、有垃圾评论,索性关了
      2、goto 只是为了省一次相同的代码,在实际代码中是不建议用的
      3、和代码比较有点类似,连续相同的作为输出,并不是查找字符的出现次数。其实是两个字符串,找出连续相同的字符

      回复
      1. @zgcwkj

        垃圾评论,可以装 CommentFilter 插件过滤一下

        哦,那应该是公共子串的概念吧。

        回复
        1. @LukaChen

          谢了哈,装了~

          回复
Top