Reverse String II - LeetCode
A very error-prone problem: https://leetcode.com/problems/reverse-string-ii/description/
Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.
Example:
Input: s = "abcdefg", k = 2 Output: "bacdfeg"
The problem description is describing the algorithm, but the pain in the lower back is to get the details coded up well. First build a Reverse function (private) to facilitate your life. Then try to follow the algorithm in the description as close as possible. Then submit it, and go to sleep. Good night! Marcelo
public class Solution
{
public string ReverseStr(string s, int k)
{
string retVal = "";
for (int from = 0; from < s.Length; from += (2 * k))
{
if (from + 2 * k < s.Length)
{
retVal += Reverse(s, from, from + k - 1);
retVal += s.Substring(from + k, k);
}
else if (from + k > s.Length)
{
retVal += Reverse(s, from, s.Length - 1);
}
else
{
retVal += Reverse(s, from, from + k - 1);
retVal += s.Substring(from + k);
}
}
return retVal;
}
private string Reverse(string s, int from, int to)
{
if (String.IsNullOrEmpty(s)) return s;
StringBuilder sb = new StringBuilder(s.Substring(from, to - from + 1));
int b = 0;
int e = sb.Length - 1;
while (b <= e)
{
char temp = sb[b];
sb[b] = sb[e];
sb[e] = temp;
b++;
e--;
}
return sb.ToString();
}
}
I guess some languages work better for this problem. My C++ solution :)
ReplyDeleteclass Solution {
public:
string reverseStr(string& s, int k) {
int step = k << 1;
for (int start = 0; start < s.size(); start += step) {
reverse(s.begin() + start, s.begin() + min(start + k, (int) s.size()));
}
return s;
}
};
Cheers,
Taras
Oh wow indeed much more succinct
ReplyDelete