LeetCode Design Compressed String Iterator

LeetCode Design Compressed String Iterator

Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext.

The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.

next() - if the original string still has uncompressed characters, return the next letter; Otherwise return a white space.
hasNext() - Judge whether there is any letter needs to be uncompressed.

Note:
Please remember to RESET your class variables declared in StringIterator, as static/class variables are persisted across multiple test cases. Please see here for more details.

Example:

StringIterator iterator = new StringIterator("L1e2t1C1o1d1e1");

iterator.next(); // return 'L'
iterator.next(); // return 'e'
iterator.next(); // return 'e'
iterator.next(); // return 't'
iterator.next(); // return 'C'
iterator.next(); // return 'o'
iterator.next(); // return 'd'
iterator.hasNext(); // return true
iterator.next(); // return 'e'
iterator.hasNext(); // return false
iterator.next(); // return ' '

本题设计了一种压缩字符串格式,即把多个连续相同字符用单个字符已经频率代替了,比如"L1e2t1C1o1d1e1"展开其实就是"LeetCode"。现在要针对这种压缩字符串,设计一个迭代器,实现next和hasNext函数。

我一开始上暴力,即首先把压缩字符串展开成常规字符串,然后直接下标操作。代码如下:

class StringIterator {
private:
	string line;
	int cur, n;
public:
	StringIterator(string compressedString) {
		line = "";
		cur = n = 0;
		vector<char> letters;
		vector<int> rep;
		string digits = "";
		for (int i = 0; i < compressedString.size(); ++i) {
			if (isalpha(compressedString[i])) {
				letters.push_back(compressedString[i]);
				if (digits != "") {
					rep.push_back(atoi(digits.c_str()));
					digits = "";
				}
			}
			else digits += string(1, compressedString[i]);
		}
		rep.push_back(atoi(digits.c_str()));
		for (int i = 0; i < letters.size(); ++i) {
			line += string(rep[i], letters[i]);
		}
		n = line.size();
	}

	char next() {
		if (cur < n)return line[cur++];
		else return ' ';
	}

	bool hasNext() {
		return cur < n;
	}
};

本代码MLE了。因为有个样例是“a1234567890b1234567890”,我表示无语,如果展开确实会MLE。

其实写上面的代码的时候我就知道可以优化,不对压缩字符串展开,而是表示成(a,1234567890)和(b,1234567890),next的时候只对频率递减。这样只需要存储少量字符以及对应的频率。

代码如下:

typedef long long ll;

class StringIterator {
private:
	int cur, n;
	vector<char> letters;
	vector<ll> rep;
public:
	StringIterator(string compressedString) {
		cur = n = 0;

		string digits = "";
		for (int i = 0; i < compressedString.size(); ++i) {
			if (isalpha(compressedString[i])) {
				letters.push_back(compressedString[i]);
				if (digits != "") {
					rep.push_back(atoll(digits.c_str()));
					digits = "";
				}
			}
			else digits += string(1, compressedString[i]);
		}
		rep.push_back(atoi(digits.c_str()));
		n = letters.size();
	}

	char next() {
		if (rep[cur] > 0) {
			char ans = letters[cur];
			--rep[cur];
			return ans;
		}
		else {
			if (cur == n - 1)return ' ';
			else {
				char ans = letters[++cur];
				--rep[cur];
				return ans;
			}
		}
	}

	bool hasNext() {
		return cur < n - 1 || (cur == n - 1 && rep[cur] > 0);
	}
};

本代码提交AC,用时13MS。

Leave a Reply

Your email address will not be published. Required fields are marked *