This is the 21st day of my participation in the August More Text Challenge

Leetcode -443- Compressed string

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

Given a character array chars, compress it using the following algorithm:

Start with an empty string s. For each group of consecutive repeating characters in chars:

If the length is 1, the character is appended to s. Otherwise, you need to append a character to s, followed by the length of the group.

The compressed string S should not be returned directly and needs to be dumped into the character array chars. Note that if the length is 10 or more, it is split into multiple characters in the CHars array.

After modifying the input array, return the new length of the array.

You must design and implement an algorithm that uses only constant extra space to solve this problem.

Example 1:

Input: chars = [" a ", "a", "b", "b", "c", "c", "c"] output: return to 6, the input of the array before 6 characters should be: [" a ", "2", "b", "2", "c", "3"] explains: "aa" is replaced by "a2"." "Bb" is replaced by "b2". "CCC" is replaced by "C3".Copy the code

Example 2:

Input: chars = ["a"] Output: returns 1, the first character of the input array should be: ["a"] Explanation: No strings are substituted.Copy the code

Example 3:

Input: chars = [" a ", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b"] output: return 4, input array should be the first four characters: [" a ", "b", "1", "2"]. Explanation: The character "a" is not compressed because it is not repeated. BBBBBBBBBBBB "is replaced by" B12 ". Note that each number has its own place in the array.Copy the code

Tip:

• 1 <= chars.length <= 2000
• Chars [I] can be a lowercase letter, a uppercase letter, a number, or a symbol

Related Topics

• Double pointer
• string
• 👍 👎 0 217

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Double pointer + extra space

• Define stringBuilder with two Pointers “I” and “j”
• The StringBuilder is responsible for logging the string representation left behind
• I j records the unknowns of the current character and the next character respectively
• Defines the number of consecutive occurrences of a CNT record character
• After recording, assign the String of StringBuilder to the input array
• Returns the stringBuilder length

public int compress(char[] chars) {
    int n = chars.length;
    //corner case
    if (n <= 1) {
        return n;
    }
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < n) {
        char temp = chars[i];
        int j = i + 1, cnt = 1;
        while (j < n && chars[j] == temp) {
            j++;
            cnt++;
        }
        i = j;
        sb.append(temp);
        if (cnt > 1) {
            sb.append(cnt);
        }
    }
    String res = sb.toString();
    char[] temp = res.toCharArray();
    for (int j = 0; j < temp.length; j++) {
        chars[j] = temp[j];
    }
    return res.length();
}
Copy the code

• Time complexity O(n)
• Space complexity O(n)

Idea two: double pointer + place replacement

• With a double pointer, “IDx”, “I”
• Records the new array index and the next judged alphabetic index respectively

public int compress(char[] chars) {
            int n = chars.length;
            //corner case
            if (n <= 1) {
                return n;
            }
            int idx = 0, i = 0;
            while (i < n) {
                char temp = chars[i];
                chars[idx] = temp;
                idx++;
                int tempIdx = idx;
                int j = i + 1, cnt = 1;
                while (j < n && chars[j] == temp) {
                    j++;
                    cnt++;
                }
                if (cnt > 1) {
                    while(cnt ! =0) {
                        chars[idx++] = (char) ((cnt % 10) + '0');
                        cnt /= 10;
                    }
                    reverse(chars, tempIdx, idx - 1);
                }
                i = j;
            }
            return idx;
        }

        void reverse(char[] cs, int start, int end) {
            while (start < end) {
                chart = cs[start]; cs[start] = cs[end]; cs[end] = t; start++; end--; }}Copy the code

• Time complexity O(n)
• Space complexity O(1)