This is the 20th day of my participation in the August Text Challenge.More challenges in August

Topic describes

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, 6 characters before input array should be: [" a ", "2", "b", "2", "c", "3"] explains: "aa" is replaced by "a2"." "Bb" is replaced by "b2". "CCC" is replaced by "C3". Source: LeetCode Link: https://leetcode-cn.com/problems/string-compression Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • Today’s daily problem is still a string problem. According to the meaning of the problem, the compression algorithm has been given, we need to implement the code according to the compression algorithm.
  • First, use the naive solution to complete the compression of strings and use StringBuilder to improve efficiency. After the compression is complete, the original array is overwritten and the result is returned.
  • But they want to use only constant extra space, so the naive solution doesn’t work. Array-related problems generally use double Pointers to optimize code.

Through the code

  • Simple solution
    public int compress(char[] chars) {
        StringBuilder builder = new StringBuilder();
        int n = chars.length;
        char temp = chars[0];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (temp == chars[i]) {
                cnt++;
            } else {
                builder.append(temp);
                if(cnt ! =1) {
                    builder.append(cnt);
                }
                temp = chars[i];
                cnt = 1;
            }
        }
        
        builder.append(temp);
        if(cnt ! =1) {
            builder.append(cnt);
        }

        String s = builder.toString();
        int ans = s.length();
        for (int i = 0 ; i < ans; i++) {
            chars[i] = s.charAt(i);
        }
        return ans;
    }
Copy the code
  • Double pointer solution
    public int compress(char[] chars) {
        int n = chars.length;
        int i = 0; 
        int j = 0;
        while (i < n) {
            int idx = i;
            while (idx < n && chars[idx] == chars[i]) {
                idx++;
            }
            int cnt = idx - i;
            chars[j++] = chars[i];
            if (cnt > 1) {
                int start = j, end = start;
                while(cnt ! =0) {
                    chars[end++] = (char) ((cnt % 10) + '0');
                    cnt /= 10;
                }
                reverse(chars, start, end - 1);
                j = end;
            }
            i = idx;
        }

        return j;
    }

    public 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

conclusion

  • The naive solution is O(n) in time and O(n) in space.
  • The time complexity of the two-pointer solution is O(n), the space complexity is O(1)
  • Adhere to the algorithm of the day, come on!