This question got asked by Monjim interview, I am able to do with brute force with time complexity of o(n2).
这个问题是Monjim面试时问到的,我可以用蛮力来做,时间复杂度为O(n2)。
Solution is -
解决方案是-
private static String wordCount(String word){
String result = "";
int k = 0;
for(int i = 0 ; i < word.length() ; i++){
char temp = word.charAt(i);
result += temp;
int count = 0;
while(k < word.length() && word.charAt(k) == temp){
k++;
count++;
temp = word.charAt(i);
}
i=k;
result += count;
}
return result;
}
Can anyone help me out with lesser time complexity.....
有没有人能帮我减少时间复杂性……
更多回答
are you sure that is O(n²)
and not O(n)
? The outer loop is being skipped as often as the inner loop is being executed
您确定这是O(n?)而不是O(N)吗?跳过外循环的次数与执行内循环的次数一样多
but it has an error: infinite loop (for example with word "abc"
) - maybe because k
is not being set to i
(or incremented) before starting the inner loop (that loop can actually be changed to use i
directly no need for k
)
但它有一个错误:无限循环(例如,使用单词“abc”)--可能是因为在开始内部循环之前,k没有设置为i(或递增)(该循环实际上可以更改为直接使用i,不需要k)。
actually just change i=k;
to i = k - 1;
( ì` will be incremented on next iteration) and it should work fine (and O(n)
)
实际上,只需将i=k;改为i = k - 1;(在下一次迭代中,k `将递增),它应该工作得很好(并且O(n))
This is already O(n), it just has a small bug.
这已经是O(N)了,它只有一个小错误。
@MadhukarH If any helped you solve the issue, please consider accepting one of the posted answers.
@MadhukarH如果有人帮助你解决了这个问题,请考虑接受其中一个张贴的答案。
Here is a simple, imperative way to do it.
这里有一个简单而必要的方法来做到这一点。
Initialize some fields
初始化一些字段
String s = "aaaabbccccaadd";
StringBuilder sb = new StringBuilder();
char currentChar = s.charAt(0);
int count = 1;
- iterate over the string, counting until the character changes
- then append the character and the count to the StringBuilder. Then reset the
count
to 1
and assign thisChar
to currentChar
- once the loop is done.
- append the last character and its count.
for (int i = 1; i < s.length(); i++) {
char thisChar = s.charAt(i);
if (currentChar == thisChar) {
count++;
} else {
sb.append(currentChar).append(count);
count = 1;
currentChar = thisChar;
}
}
sb.append(currentChar).append(count);
System.out.println(sb);
prints
指纹
a4b2c4a2d2
And here is a solution using regular expressions.
这里有一个使用正则表达式的解决方案。
(.)
capture a single character
(\\1)*
followed by zero or more of the same character (uses a backreference).
- then append
group(1)
, the single character followed by the length of the entire group(0)
.
Matcher matcher = Pattern.compile("(.)(\\1)*").matcher(s);
StringBuilder sb = new StringBuilder();
while(matcher.find()) {
sb.append(matcher.group(1)).append(matcher.group(0).length());
}
System.out.println(sb);
prints
指纹
a4b2c4a2d2
You can reduce the iterations, at least, by simply checking for a character change.
In your code, you are spawning a new loop, starting at k.
您至少可以通过简单地检查字符更改来减少迭代次数。在您的代码中,您正在产生一个新的循环,从k开始。
Here is an example.
这里有一个例子。
char[] chars = "aaaabbccccaadd".toCharArray();
char c;
StringBuilder s = new StringBuilder();
s.append(c = chars[0]);
int b = 1;
for (int i = 1, n = chars.length; i < n; i++) {
if (chars[i] == c) b++;
else {
if (b != 1) s.append(b);
b = 1;
s.append(c = chars[i]);
}
}
s.append(b);
Your code will execute the same example string, "aaaabbccccaadd" in 19 iterations.
Whereas, this will execute it in 13.
您的代码将在19次迭代中执行相同的示例字符串“aaaabbccccaadd”。而这将在13年内执行。
I have a few recommendations for your code.
我对您的代码有几点建议。
Utilize variable declaration chains, and append k as a for-loop variable.
And, define a length variable to prevent the loop from calling word.length on every iteration.
利用变量声明链,并将k附加为for循环变量。并且,定义一个长度变量,以防止循环在每次迭代时调用word.long。
for(int i = 0, k = 0, n = word.length() ; i < n ; i++)
Also, declare temp outside of the for-loop, and place count as an additional variable.
此外,在for循环之外声明temp,并将count作为附加变量放置。
char temp;
for(int i = 0, k = 0, n = word.length(), count ; i < n ; i++)
Here is the re-factor.
以下是重新考虑的因素。
String result = "";
char temp;
for(int i = 0, k = 0, n = word.length(), count ; i < n ; i++){
temp = word.charAt(i);
result += temp;
count = 0;
while(k < n && word.charAt(k) == temp){
k++;
count++;
temp = word.charAt(i);
}
i=k;
result += count;
}
return result;
With "aaaabbccccaadd" and the answer is "a4b2c4a2d2", I assume this is counting the consecutive words occurrance right? if so then you just need one loop O(n).
对于“aaaabbccccaadd”,答案是“a4b2c4a2d2”,我假设这是在计算连续出现的单词,对吗?如果是这样,那么您只需要一个循环O(N)。
private static String wordCount(String word){
if (word.isEmpty()) return "";
String result = "";
int k = 0;
char currentChar = word.charAt(0);
for(int i = 0 ; i < word.length() ; i++){
if (currentChar != word.charAt(i)) {
result += currentChar;
result += String.valueOf(k);
currentChar = word.charAt(i);
k = 1;
} else {
k++;
}
}
result += currentChar;
result += String.valueOf(k);
return result;
}
更多回答
regular expression solution is awesome, thanks !!
正则表达式解决方案太棒了,谢谢!
This is still O(n^2). Copying strings is O(n).
这仍然是O(n^2)。复制字符串的时间为O(N)。
我是一名优秀的程序员,十分优秀!