Shortest Palindrome

https://leetcode.com/problems/shortest-palindrome/

[TODO] read others’ KMP algorithm and completely undersstand it.

Used StefanPochmann’s post: https://discuss.leetcode.com/topic/14542/ac-in-288-ms-simple-brute-force


class Solution(object):
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
r = s[::-1]#this means to reverse the string `s` completely
for i in range(len(s)+1):
if s.startswith(r[i:]):
return r[:i] + s;

I wrote my own naive program and made it to 116/119 test cases, but got TLE at this test case: “aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa…………….”

My idea was:

  • check the given string s from its first char to its char at index s.length/2, mark the char that is working as the pivot point which its left substring and right substring are equal, thus forming a palindrome, then I just add the remaining chars to the original string’s head and return it.
  • for pivot1 and pivot2, that is for dealing with two different cases of palindromes:
    • case1: s = “abcd“, should return “dcbabcd”
    • case2: s = “aabba”, should return “abbaabba”

Here’s my naive program:


public String shortestPalindrome(String s) {
if(s == null || s.length() < 2) return s;

int pivot1 = 0;
int pivot2 = 0;
if(isPalindrome(s)) return s;
for(int i = 1; i < s.length()/2; i++){
if(isPalindrome(s, i)){
pivot1 = i;
}
else if(isPalindrome_symmetric(s, i)){
pivot2 = i+1;
}
}
if(pivot2 != 0){
String filled = s.substring(2*pivot2);
String reversedFilled = new StringBuilder(filled).reverse().toString();
return new StringBuilder(reversedFilled).append(s).toString();
} else {
if(pivot1 == 0 && s.charAt(0) == s.charAt(1)){
String filled = s.substring(2*pivot1+2);
String reversedFilled = new StringBuilder(filled).reverse().toString();
return new StringBuilder(reversedFilled).append(s).toString();
} else {
String filled = s.substring(2*pivot1+1);
String reversedFilled = new StringBuilder(filled).reverse().toString();
return new StringBuilder(reversedFilled).append(s).toString();
}
}
}

private boolean isPalindrome_symmetric(String s, int index) {
String left = s.substring(0, index+1);
String right = s.substring(index+1, (index+1)*2);
return new StringBuilder(left).reverse().toString().equals(right);
}

private boolean isPalindrome(String s) {
String left = s.substring(0, s.length()/2);
String right = s.substring(s.length()/2+1);
return new StringBuilder(left).reverse().toString().equals(right);
}

boolean isPalindrome(String s, int index){
String left = s.substring(0, index);
String right = s.substring(index+1, index*2+1);
return new StringBuilder(left).reverse().toString().equals(right);
}

Advertisements

Find K Pairs with Smallest Sums

https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

StefanPochmann won again, amazed by his post: https://discuss.leetcode.com/topic/50450/slow-1-liner-to-fast-solutions

First off, as StefanPochmann pointed out, “I found it helpful to visualize the input as an m×n matrix of sums, for example for nums1=[1,7,11], and nums2=[2,4,6]:”

2  4  6
+————
1   | 3  5  7
7  | 9 11 13
11 | 13 15 17

The above very visually friendly matrix is the basis for the following understanding/algorithms:

Approach 1: use a heap (a priority queue in Java) to store the next possible candidates and pop them out in ascending order.

  • The number in the above matrix means the sum from the two given arrays, i.e. m[0][1] = 5 = 1+4 = nums1[0] + nums2[1]
  • After finding the first smallest sum which is at m[0][0], the next smallest possible sums are at m[0][1] or m[1][0], which one pop() first? we use a PriorityQueue (minHeap) to achieve this.
  • We need to create a new class called Node to denote each point in the matrix
  • We need to implement the so-called anonymous comparator in the newly created Node class: compare the node class based on its sum
  • How does the min heap or the PriorityQueue in Java come into play?
    • there might be multiple candidates in the queue for the poll() action, which one poll() first? the one with the highest priority, i.e. based on how we customize the comparator function.
  • We do a BFS starting from (0,0) and mark each visited node to avoid re-visit.

Inspired by this post: https://discuss.leetcode.com/topic/50435/java-easy-understandable-bfs-with-priorityqueue


public class Solution {
final int[][] neighbors = new int[][]{{1,0}, {0,1}};
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> result = new ArrayList<int[]>();
if(nums1 == null || nums2 == null || k == 0 || nums1.length == 0 || nums2.length == 0) return result;
Queue<Node> meanHeap = new PriorityQueue<Node>();
meanHeap.offer(new Node(0, 0, nums1[0] + nums2[0]));
boolean[][] visited = new boolean[nums1.length][nums2.length];
visited[0][0] = true;//we start form (0,0), so mark it as visited
while(k > 0 && !meanHeap.isEmpty()){
Node node = meanHeap.poll();
result.add(new int[]{nums1[node.row], nums2[node.col]});
k--;
for(int[] neighbor : neighbors){
int nextRow = node.row + neighbor[0];
int nextCol = node.col + neighbor[1];
if(nextRow < 0 || nextCol < 0 || nextRow >= nums1.length || nextCol >= nums2.length || visited[nextRow][nextCol]) continue;
visited[nextRow][nextCol] = true;
meanHeap.offer(new Node(nextRow, nextCol, nums1[nextRow] + nums2[nextCol]));
}
}
return result;
}

private class Node implements Comparable<Node>{
int row;
int col;
int sum;

public Node(int row, int col, int sum){
this.row = row;
this.col = col;
this.sum = sum;
}

@Override
public int compareTo(Node that) {
return this.sum - that.sum;
}
}
}

 

 

Approach 2: brute force, enumerate all of the products and sort them, return the first k, I thought of doing it in Java, using a HashMap to store int[] as key and product as value, and then sort the map based on its values and then return the first k keys. But I’ll have to write my own comparator to do the sorting. Then I turned to StefanPochmann’s super clean python code:


def kSmallestPairs(self, nums1, nums2, k):

return sorted(itertools.product(nums1, nums2), key=sum)[:k]

Notes about Python for beginners

 

 

  1. if a method is inside a class, it MUST take self parameter in its method signature
    •  def func(self, arg1, arg2)
    • the reason for using self is because it makes it super clear that this method is referring to this current object. Kind of similar to this keyword in Java.
  2.  https://www.hackerrank.com/challenges/finding-the-percentage
    • The key thing that I learned from this exercise is that in order to print out an integer to two decimal places precision, you’ll have to specify “%.2f” in your print statement, otherwise, 56 will just be printed out as 56.0, not 56.00.

N = int(raw_input())
new_dict = {}
for i in range(N):
strings = raw_input().split()
score = map(float, strings[1:])
new_dict[strings[0]] = sum(score)/float(len(score))

print "%.2f" % round((new_dict[raw_input()]),2)