题目地址:https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
题目描述
请实现一个函数,把字符串 s
中的每个空格替换成"%20"。
题目示例
输入:s = "We are happy."
输出:"We%20are%20happy."
解题思路
思路1:遍历字符串,查找空字符,并替换空字符为"%20",需要额外辅助空间;
思路2:双指针法。遍历字符串,并统计空字符个数,将字符串数组的大小扩充为添加”%20“之后的大小,然后从后往前遍历替换空格即可。
程序源码
思路11
//时间复杂度O(N),空间复杂度O(N)
class Solution { public: string replaceSpace(string s) { if(s.empty()) return s; string str; for(int i = 0; i < s.size(); ++i) { if(s[i] == ' ') str += "%20"; else str += s[i]; } /* for(auto &c : s) { if(c == ' ') { str.push_back('%'); str.push_back('2'); str.push_back('0'); } else str.push_back(c); }*/ return str; } };
思路2
//时间复杂度O(N),空间复杂度O(1)
class Solution { public: string replaceSpace(string s) { if(s.empty()) return s; int cnt = 0; //统计空字符个数 int oldSize = s.size(); for(auto &c : s) { if(c == ' ') cnt++; } s.resize(oldSize + cnt * 2); int newSize = s.size(); for(int i = oldSize - 1, j = newSize - 1; i < j; --i, --j) { if(s[i] != ' ') { s[j] = s[i]; } else { s[j] = '0'; s[j - 1] = '2'; s[j - 2] = '%'; j -= 2; } } return s; } };