StringBuilder III
Another example where string concatenation leads to TLE while the StringBuilder approach gets to the expected solution. A lot of concatenations using Strings in C# will lead to many objects being created all the time, which not only wastes memory but also time in the process (including GC). This article from SO discusses this theme well: c# - benefits of using a stringbuilder - Stack Overflow
Code is down below, cheers, ACC
String Compression III - LeetCode
Given a string word, compress it using the following algorithm:
- Begin with an empty string
comp. Whilewordis not empty, use the following operation:- Remove a maximum length prefix of
wordmade of a single charactercrepeating at most 9 times. - Append the length of the prefix followed by
ctocomp.
- Remove a maximum length prefix of
Return the string comp.
Example 1:
Input: word = "abcde"
Output: "1a1b1c1d1e"
Explanation:
Initially, comp = "". Apply the operation 5 times, choosing "a", "b", "c", "d", and "e" as the prefix in each operation.
For each prefix, append "1" followed by the character to comp.
Example 2:
Input: word = "aaaaaaaaaaaaaabb"
Output: "9a5a2b"
Explanation:
Initially, comp = "". Apply the operation 3 times, choosing "aaaaaaaaa", "aaaaa", and "bb" as the prefix in each operation.
- For prefix
"aaaaaaaaa", append"9"followed by"a"tocomp. - For prefix
"aaaaa", append"5"followed by"a"tocomp. - For prefix
"bb", append"2"followed by"b"tocomp.
Constraints:
1 <= word.length <= 2 * 105wordconsists only of lowercase English letters.
public string CompressedString(string word)
{
if (String.IsNullOrEmpty(word)) return word;
char prev = word[0];
int count = 1;
int MAX = 9;
StringBuilder retVal = new StringBuilder();
for (int i = 1; i < word.Length; i++)
{
if (word[i] != prev || count >= MAX)
{
retVal.Append((char)(count + (int)'0'));
retVal.Append(prev);
count = 0;
}
prev = word[i];
count++;
}
retVal.Append((char)(count + (int)'0'));
retVal.Append(prev);
return retVal.ToString();
}
Comments
Post a Comment
[γγ¬γΌγ ]