java给定2个字符串,只删除一个数字,使1个字符串按字典顺序变小
我试图解决Java中字符串操作的编码问题。问题是
Given two strings S and T consisting of digits and lowercase letters, you are allowed to remove only one digit from either string, count how many ways of removal to make S lexicographically smaller than T.
我自己提出了这个测试用例。如果s='3ab'和t='cd',则返回1。如果s='123ab'和t='423cd',则返回6
我的想法是使用2作为循环,通过检查字符是否为数字来遍历每个字符串,将其删除并与另一个字符串进行比较
private static int numSmaller(String s, String t){
int ways = 0;
for(int i = 0; i < s.length(); i++){
StringBuilder sbs = new StringBuilder(s);
if(Character.isDigit(s.charAt(i))){
sbs.deleteCharAt(i);
String sub = sbs.toString();
if(sub.compareTo(t) < 0) {
ways++;
}
}
}
for(int i = 0; i < t.length(); i++){
StringBuilder sbt = new StringBuilder(t);
if(Character.isDigit(t.charAt(i))){
sbt.deleteCharAt(i);
String sub = sbt.toString();
if(s.compareTo(sub) < 0){
ways++;
}
}
}
return ways;
}
正如您所看到的,空间复杂度非常糟糕,而且代码似乎也是冗余的。有没有办法优化这段代码?有没有人发现了一种方法,可以避免每次使用字符串生成器或创建新字符串?欢迎您的任何意见
# 1 楼答案
我使用了
streams
并将其与您使用长度为10的随机字符串的方法进行了比较。我运行了这些字符串的1 million
测试用例,这两种方法提供了相同的结果流部分相当简单。我使用
IntStream
索引到字符串中,根据数字位置构建substrings
。然后,我根据传递的BiFunction
lambda进行过滤,该lambda充当双参数谓词。在此基础上,我计算成功的次数我做了两次,反转参数和谓词逻辑,并总结这两个计数
# 2 楼答案
仅依赖于检查第一个字符的O(n+m)解决方案对此输入失败
只检查第一个字符仍然是一个很大的改进,但是必须处理边缘情况
# 3 楼答案
以下是具有
O(n+m)
时间复杂性的工作解决方案。只有第一个字符是重要的,我们可以根据它的数量来决定如何处理它# 4 楼答案
# 5 楼答案
您可以将时间复杂度降低到O(m+n),其中m,n是S,T的长度 我写了C++代码,并测试了它的工作原理。p>
其目的是比较S和T的第一个字符: