“ alphaNumeric”函数的输入是一个字符串，由所有小写的字母数字字符组成，例如“ hello123hello”。我希望能够通过check（）函数检查此字符串的所有大写/小写字母组合。（例如HeL10123hELlo是要检查的组合之一）。我已经用Java编写了代码，将匹配的String存储到ArrayList中，但是想知道如果没有ArrayList，是否有更好的方法可以做到这一点。另外，我说最坏的情况是O（2 ^ n）正确吗？注意：Check是一个返回true或false的函数，具体取决于是否将正确的String传递给该函数。
public static String alphaNumeric(String input) {
ArrayList<String> list = new ArrayList<String>();
alphaHelper(input, "", list);
return list.get(0);
}
private static void alphaHelper(String in, String current, ArrayList<String> list) {
if (in.length() == 0) {
if (check(current)) {
list.add(current);
}
} else if (Character.isLetter(in.charAt(0))) {
alphaHelper(in.substring(1),current+in.substring(0,1).toLowerCase(),list);
alphaHelper(in.substring(1),current+in.substring(0,1).toUpperCase(),list);
} else if (Character.isDigit(in.charAt(0))) {
alphaHelper(in.substring(1),current+in.substring(0,1),list);
} else {
return;
}
}
如果您只想删除ArrayList而不更改基本算法，则可以执行以下操作：
public static String alphaNumeric(String input) {
return alphaHelper(input, "");
}
private static String alphaHelper(String in, String current) {
String result = null;
if (check(current)) {
result = current;
} else if (Character.isLetter(in.charAt(0))) {
result = alphaHelper(in.substring(1),current+in.substring(0,1).toLowerCase());
if (result == null) result = alphaHelper(in.substring(1),current+in.substring(0,1).toUpperCase());
} else if (Character.isDigit(in.charAt(0))) {
result = alphaHelper(in.substring(1),current+in.substring(0,1));
}
return result;
}
是的，它是O（2 ^ n），如果您不能直接获得原始字符串，我看不到如何改进。
如果您不需要检查子字符串（即，您只关心整个字符串的大小写变化），则可以通过不测试子字符串来改进算法，但是它仍然是O（2 ^ n）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句