时间戳

首页 > 解决方案 > 如何比较两个字符串以找到公共子字符串

java - 如何比较两个字符串以找到公共子字符串

问题描述

我编译时由于超时错误而终止。请帮我

给定两个字符串，确定它们是否共享一个公共子字符串。一个子字符串可以小到一个字符。

例如，单词 "a"、"and"、"art" 共享公共子字符串 "a" 。“be”和“cat”这两个词不共享子字符串。

输入格式

第一行包含一个整数，即测试用例的数量。

以下成对的行如下：

第一行包含字符串 s1 。第二行包含字符串 s2 。

输出格式

对于每对字符串，返回 YES 或 NO。

我在java中的代码

public static void main(String args[])
{
    String s1,s2;
    int n;
    Scanner s= new Scanner(System.in);
    n=s.nextInt();
    while(n>0)
    {    
    int flag = 0;
        s1=s.next();

    s2=s.next();
    for(int i=0;i<s1.length();i++)
    {
        for(int j=i;j<s2.length();j++)
        {
            if(s1.charAt(i)==s2.charAt(j))
            {
                flag=1;
            }
        }
    }


        if(flag==1)
        {
            System.out.println("YES");
        }
        else
        {
            System.out.println("NO");
        }
        n--;
}
}

}

有小费吗？

标签： javastring

解决方案

超时的原因可能是：要比较两个每个长度为 1.000.000 个字符的字符串，您的代码总是需要 1.000.000 * 1.000.000 次比较。

有一种更快的算法，只需要 2 * 1.000.000 次比较。您应该改用更快的算法。它的基本思想是：

  • 对于 s1 中的每个字符：将字符添加到集合中（这是第一个百万）
  • 对于 s2 中的每个字符：测试步骤 1 中的集合是否包含该字符，如果是，则立即返回“是”（这是第二个百万）

Java 已经提供了一种可以满足您所有需要的 BitSet 数据类型。它是这样使用的：

BitSet seenInS1 = new BitSet();
seenInS1.set('x');
seenInS1.get('x');

推荐阅读