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.....

有没有人能帮我减少时间复杂性……

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;
}