3

我有一个字符串列表，对于每个字符串，我想对照其他字符串检查它的字符，以查看除了一个之外，它的所有字符是否相同。

例如，将返回 true 的检查将是检查

岩石对着锁

时钟和羊群有一个不同的特征，不多不少。

岩石对凹痕显然会返回错误。

我一直在考虑首先遍历列表，然后在其中有一个辅助循环来检查第一个字符串与第二个字符串。

然后使用split("");创建两个包含每个字符串的字符的数组，然后将数组元素相互检查（即将每个字符串与另一个数组 1-1 2-2 等中的相同位置进行比较...），只要只有一个字符比较失败，那么对这两个字符串的检查为真。

无论如何，我有很多字符串（4029），考虑到我目前正在考虑实现的内容将包含 3 个循环，每个循环都包含在另一个循环中，这将导致一个立方循环（？），这需要很长时间才能使用这么多元素不会吗？

有没有更简单的方法来做到这一点？或者这种方法真的可以吗？或者 - 希望不是 - 但我提出的解决方案是否存在某种潜在的逻辑缺陷？

非常感谢！

4

5 回答 5

5

为什么不以天真的方式去做呢？

bool matchesAlmost(String str1, String str2) {
    if (str1.length != str2.length)
        return false;
    int same = 0;
    for (int i = 0; i < str1.length; ++i) {
        if (str1.charAt(i) == str2.charAt(i))
            same++;
    }
    return same == str1.length - 1;
}

现在您可以使用二次算法来检查每个字符串。

于 2012-10-14T15:31:04.040 回答
0

假设两个字符串的长度相等

String str1 = "rock";
        String str2 = "lick";

        if( str1.length() != str2.length() )
            System.out.println( "failed");

        else{
            if( str2.contains( str1.substring( 0, str1.length()-1)) || str2.contains(  str1.substring(1, str1.length() )) ){
                System.out.println( "Success ");
            }

            else{
                System.out.println( "Failed");
            }
        }
于 2012-10-14T15:35:29.000 回答
0

不确定这是否是最好的方法，但即使两个字符串长度不同，这种方法也有效。例如： cat & cattp 它们相差一个字符 p 而 t 是重复的。看起来像 O(n) 时间解决方案，为 hashmap 和字符数组使用了额外的空间。

/**
 * Returns true if two strings differ by one character
 * @param s1 input string1
 * @param s2 input string2
 * @return true if strings differ by one character 
 */
boolean checkIfTwoStringDifferByOne(String s1, String s2) {
    char[] c1, c2;

    if(s1.length() < s2.length()){
        c1 = s1.toCharArray();
        c2 = s2.toCharArray();
    }else{
        c1 = s2.toCharArray();
        c2 = s1.toCharArray();
    }

    HashSet<Character> hs = new HashSet<Character>();

    for (int i = 0; i < c1.length; i++) {
        hs.add(c1[i]);
    }
    int count = 0;
    for (int j = 0; j < c2.length; j++) {
        if (! hs.contains(c2[j])) {
            count = count +1;
        }
    }

    if(count == 1)
        return true;
    return false;
}
于 2013-10-23T01:53:47.997 回答
0 
Best way is to concatenate strings together one forward and other one in reverse order. Then check in single loop for both ends matching chars and also start from middle towards ends matching char. If more than 2 chars mismatch break.
If one mismatch stop and wait for the next one to complete if it reaches the same position then it matches otherwise just return false. 

    public static void main(String[] args) {

        // TODO code application logic here
        New1 x = new New1();
        x.setFunc();
      }

       static void setFunc(){ 
          Set s         = new HashSet<Character>();
          String input  = " aecd";
          String input2 = "abcd";
          String input3 = new StringBuilder(input2).reverse().toString();
          String input4 = input.concat(input3);
          int length    = input4.length(); 

          System.out.println(input4);
          int flag      = 0;

          for(int i=1,j=length-1;j>i-1; i++,j--){

            if(input4.charAt(i)!=input4.charAt(j)){ 

                System.out.println(input4.charAt(i)+" doesnt match with "+input4.charAt(j));
                    if(input4.charAt(i+1)!=input4.charAt(j)){  
                         System.out.println(input4.charAt(i+1)+" doesnt match  with "+input4.charAt(j));
                         flag = 1;
                         continue; 
                    } else if( input4.charAt(i)!=input4.charAt(j-1) ){
                         System.out.println(input4.charAt(i)+" doesnt match with "+input4.charAt(j-1));
                         flag = 1;
                         break; 
                    } else if(input4.charAt(i+1)!=input4.charAt(j-1) && i+1 <= j-1){
                         System.out.println(input4.charAt(i+1)+" doesnt match with xxx "+input4.charAt(j-1));
                         flag = 1;
                         break; 
                    }
                    } else {
                      continue;
                    }
             }

              if(flag==0){
                   System.out.println("Strings differ by one place");
              } else {
                   System.out.println("Strings does not match");
              }
        }
于 2015-09-16T05:48:41.867 回答
0

假设所有字符串都具有相同的长度，我认为这会有所帮助：

public boolean differByOne(String source, String destination)
{
    int difference = 0;

    for(int i=0;i<source.length();i++)
    {
        if(source.charAt(i)!=destination.charAt(i))
        {
            difference++;

            if(difference>1)
            {
                return false;
            }
        }
    }

    return difference == 1;
}
于 2016-07-18T21:04:41.263 回答