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个规则,并了解如何为每个规则生成类似的方法,以验证是否可以应用该规则。