java - 一种算法，以检查是否最多可以通过插入或删除一个字符来从另一个字符串中获得一个字符串？

Closed. This question needs details or clarity. It is not currently accepting answers. Learn more。
想改进这个问题吗？添加细节并通过editing this post澄清问题。
我正在寻找以下Java代码性问题的答案，但我失败了：-（
给定字符串S和字符串T，返回：
“INSERT x”如果字符串S可以从字符串T获得，则最多可以插入一个字符x。
例如，当s=“nice”和t=“nice”时，方法将返回“insert e”
“delete x”如果字符串t最多可以通过删除一个字符x从字符串s获得。
例如，当S=“hell o”和T=“hell”时，方法将返回“DELETE o”
“swap x z”如果字符串t可以通过交换两个相邻字符从字符串s获得。
例如，当S=“from”和T=“form”时，该方法将返回“SWAP r o”
如果根据上述规则无法从字符串S获得字符串T，“不可能”
如果字符串T等于字符串S，“相同”
给出的方法签名是：

public static String solution(String S, String T)

这个问题表明正确性和性能是相关的，所以我想知道最干净的解决方案是什么（也就是说，不一定是最有效的）。
更新
感谢@amit在下面对交换方法的回答我现在已经有了下面列出的其他插入和删除方法，但是，我对它们不太满意，我希望对这些方法的更优雅的方法有一些建议非常感谢！

class Codility {
    public static String solution(String s1, String s2) {
        if (s1.equals(s2)) {
          return "SAME";
        }
        String result = checkIfInsertionMakesStringsEqual(s1, s2);
        if (result != null) { 
            return "INSERT " + result;
        }
        result = checkIfDeletionMakesStringsEqual(s1, s2);
        if (result != null) {
            return "DELETE " + result;
        }
        result = checkIfSwappingMakesStringsEqual(s1, s2);
        if (result != null) {
            return "SWAP " + result;
        }
        return "IMPOSSIBLE";
    }

    private static String checkIfInsertionMakesStringsEqual(final String s1, final String s2) {
        if (s1.length() + 1 != s2.length()) {
            return null;
        }
        final char[] s1AsCharArr = s1.toCharArray();
          final char[] s2AsCharArr = s2.toCharArray();

        for (int s2CharIndex = 0; s2CharIndex < s2AsCharArr.length; s2CharIndex++) {
            if (s2CharIndex == s2AsCharArr.length-1) { //deal with corner case, at last char in s2
                final String s1WithCharInserted = s1 + s2AsCharArr[s2CharIndex];
                if (s1WithCharInserted.equals(s2)) {
                  return String.valueOf(s2AsCharArr[s2CharIndex]);
                } else {
                  return null;
                }
            }
            if (s1AsCharArr[s2CharIndex] != s2AsCharArr[s2CharIndex]) {
                final String s1WithCharInserted = 
                    s1.substring(0, s2CharIndex) + s2AsCharArr[s2CharIndex] + s1.substring(s2CharIndex, s1AsCharArr.length);
                if (s1WithCharInserted.equals(s2)) {
                  return String.valueOf(s2AsCharArr[s2CharIndex]);
                } else {
                  return null;
                }
            } else {
              continue;
            }
        }

        return null;
    }

  private static String checkIfDeletionMakesStringsEqual(final String s1, final String s2) {
        if (s1.length() - 1 != s2.length()) {
            return null;
        }
        final char[] s1AsCharArr = s1.toCharArray();
          final char[] s2AsCharArr = s2.toCharArray();

        for (int s1CharIndex = 0; s1CharIndex < s1AsCharArr.length; s1CharIndex++) {
            if (s1CharIndex == s1AsCharArr.length-1) { //deal with corner case, at last char in s1
                final String s1WithCharDeleted = s1.substring(0, s1AsCharArr.length-1);
                if (s1WithCharDeleted.equals(s2)) {
                  return String.valueOf(s1AsCharArr[s1CharIndex]);
                } else {
                  return null;
                }
            }
            if (s1AsCharArr[s1CharIndex] != s2AsCharArr[s1CharIndex]) {
                final String s1WithCharDeleted = 
                    s1.substring(0, s1CharIndex) + s1.substring(s1CharIndex+1, s1AsCharArr.length);
                if (s1WithCharDeleted.equals(s2)) {
                  return String.valueOf(s1AsCharArr[s1CharIndex]);
                } else {
                  return null;
                }
            } else {
              continue;
            }
        }

        return null;
    }

    private static String checkIfSwappingMakesStringsEqual(final String s1, final String s2) {
        if (s1.length() != s2.length()) {
            return null;
        }
        final char[] s1AsCharArr = s1.toCharArray();
        for (int s1CharIndex = 0; s1CharIndex < s1AsCharArr.length - 1; s1CharIndex++) {
            swapArrElements(s1AsCharArr, s1CharIndex, s1CharIndex + 1);
            if (s2.equals(new String(s1AsCharArr))) {
                return s1AsCharArr[s1CharIndex + 1] + " " + s1AsCharArr[s1CharIndex];
            }
            swapArrElements(s1AsCharArr, s1CharIndex, s1CharIndex + 1); //reverse back to normal
        }
        return null;
    }

     private static void swapArrElements(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

最佳答案

我不想给出一个完整的答案，但我想引导你朝着正确的方向前进。
你的方法应该是这样的：

public static String findSingleChangeNaive(String s1, String s2) { 
    if (s1.equals(s2)) return "SAME";
    String res = switchWithInsert(s1,s2);
    if (res != null) return "INSERT " + res;
    res = switchWithDelete(s1, s2);
    if (res != null) return "DELETE " + res;
    res = switchWithSwap(s1, s2);
    if (res != null) return "SWAP " + res;
    return "IMPOSSIBLE";
}

它基本上是对不同方法的调用，每个方法都在检查是否可以应用某些规则来生成所需的结果。
我只举一个例子说明这种方法，因为你应该自己练习如何生成其他方法：

private static void swap(char[] arr, int i, int j) {
    char temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
private static String switchWithSwap(String s1, String s2) { 
    if (s2.length() != s1.length()) return null;
    char[] arr = s1.toCharArray();
    for (int i = 0; i < arr.length - 1; i++) { 
        swap(arr,i,i+1);
        if (s2.equals(new String(arr))) return arr[i+1] + " " + arr[i];
        swap(arr,i,i+1); //reverse back to normal
    }
    return null;
}

上面的方法尝试交换字符串中的每两个相邻元素，然后检查其是否与结果相同。非常简单和粗暴地检查你是否可以应用规则3。
这并没有得到优化，而且可以进行许多优化（比如不为每次检查创建一个新的字符串对象，对于初学者来说），但是这里的问题并不是主要关注的效率。
尝试分解其他2个规则，并了解如何为每个规则生成类似的方法，以验证是否可以应用该规则。

关于java - 一种算法，以检查是否最多可以通过插入或删除一个字符来从另一个字符串中获得一个字符串？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31045831/

上一篇：algorithm - 重新访问树上的递归函数 (DFS) 中的某些节点

下一篇：算法 - 平衡断开的二分图

相关文章：

c - C 中大型二维数组导致的段错误

javascript - RegExp.test 不工作？

java - 在 Java 中使用 BigInteger 的递归斐波那契数列

java - 我如何比较 Java 中的字符串和字符数组？

java - 为什么在这种简单的情况下静态初始化程序 block 不运行？

javascript - Protractor - 比较 2 个数组的差异

java - 根据对象列表中列表中的字段对对象列表进行排序

regex - 提取正则表达式匹配

regex - Angular 和文本掩码 : Regex to validate an input without special characters

java - 为什么要费心使用 ArrayList(int capacity)？