String manipulation ought to be avoided
Usually string manipulations such as appending, pre-pending, substring or even the equal operator can be a problem in disguise. Calling APIs to perform such operations especially in high-level languages like C# is so easy and convenient, but if you're trying to squeeze every single millisecond in perf, taking this approach won't do you any good.
Hard LeetCode problems require two aspects:
a) That you get the algorithm right
b) And that you get the constant small, really small
The following problem exemplifies the point: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
1312. Minimum Insertion Steps to Make a String Palindrome
Hard
Given a string
s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make
s palindrome.
A Palindrome String is one that reads the same backward as well as forward.
Example 1:
Input: s = "zzazz" Output: 0 Explanation: The string "zzazz" is already palindrome we don't need any insertions.
Example 2:
Input: s = "mbadm" Output: 2 Explanation: String can be "mbdadbm" or "mdbabdm".
Example 3:
Input: s = "leetcode" Output: 5 Explanation: Inserting 5 characters the string becomes "leetcodocteel".
Example 4:
Input: s = "g" Output: 0
Example 5:
Input: s = "no" Output: 1
Constraints:
1 <= s.length <= 500- All characters of
sare lower case English letters.
Accepted
3,001
Submissions
5,646
The proper algorithm to solve this would be a BFS - the moment that you find a solution, it is guaranteed to be the minimum. But if on top of that you add lots of string manipulation, which was my mistake in many of the attempts, you'll keep running into timeouts due to the heavy overhead of such operations. What I did was replace all string manipulation statements with the two pointers approach and it was enough to make the cut. Code is down below, cheers, ACC.
public class Solution
{
public int MinInsertions(string s)
{
if (String.IsNullOrEmpty(s)) return 0;
Queue<QueueItem> queue = new Queue<QueueItem>();
QueueItem qi = new QueueItem(0, s.Length - 1, 0);
queue.Enqueue(qi);
int key = qi.left * (s.Length + 1) + qi.right;
Hashtable visited = new Hashtable();
visited.Add(key, true);
while (queue.Count > 0)
{
QueueItem current = queue.Dequeue();
int left = current.left;
int right = current.right;
bool isPalindrome = true;
while (left < right)
{
if (s[left] != s[right])
{
isPalindrome = false;
break;
}
left++;
right--;
}
if (isPalindrome) return current.steps;
int key1 = (left + 1) * (s.Length + 1) + right;
if (!visited.ContainsKey(key1))
{
QueueItem rqi = new QueueItem(left + 1, right, current.steps + 1);
queue.Enqueue(rqi);
visited.Add(key1, true);
}
int key2 = left * (s.Length + 1) + (right - 1);
if (!visited.ContainsKey(key2))
{
QueueItem rqi = new QueueItem(left, right - 1, current.steps + 1);
queue.Enqueue(rqi);
visited.Add(key2, true);
}
}
return 0;
}
}
public class QueueItem
{
public int left;
public int right;
public int steps;
public QueueItem(int left, int right, int steps)
{
this.left = left;
this.right = right;
this.steps = steps;
}
}
Comments
This comment has been removed by a blog administrator.
Reply DeletePost a Comment
[γγ¬γΌγ ]