LeetCode Blog for course "Algorithms" -- Problem 3 & 5

Problem 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.


My solution in Python:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ answer = 0; left = 0; last = {}; for i in range(len(s)): if s[i] in last and last[s[i]] >= left: left = last[s[i]] +1; last[s[i]] = i; answer = max(answer, i - left + 1); return answer;

Review:
We make good use of the "dictionary" in Python here. Starting with the first character in the string, we go through the string characters one by one, and store one item in the dictionary, with the character being the key, and the place it appears in the string being the value. When we encounter a character that has already appeared previously, we immediately know because this particular key (the character) is already in the dictionary. Thus we move the starting character of the substring to the next position of which the repeated character first appeared in the original string. We then compare the length of the current non-repeated-character-substring with the longest substring we already know. When "i" reaches the last character of the original string, the "answer" should be the length of the longest substring without repeated character.


Problem 5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:
Input: "cbbd"
Output: "bb"

My solution in Python: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ ansl, ansr, maxx = 0, 0, 0 length = len(s) for i in range(1, length * 2): if i & 1 : left = i / 2 right = left else : left = i / 2 - 1 right = left + 1 while (left >= 0) and (right < length) and (s[left] == s[right]): left -= 1 right += 1 left += 1 right -= 1 if right - left > maxx: maxx = right - left ansl = left ansr = right return s[ansl: ansr + 1]

Review:
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only $\mathrm{2n-1}$ such centers. By treating odd "i" and even "i" differently, we are able to examine both palindromes with even length and with odd length. This question is actually very interesting and has many (at least 5) different solutions, each with different time and space efficiency. The most advanced one, the Manacher's algorithm, can be found here.

LeetCode Blog for course "Algorithms" -- Problem 1 & 2

Problem 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My solution in Python:

1 2 3 4 5 6 7 8 9 10

class Solution(object):     def twoSum(self,nums,target):         first=0         second=0         for x in range(0,len(nums)):             for y in range(x+1,len(nums)):                 if nums[x]+nums[y]==target:                     first=x                     second=y                     return [first,second]

Review:
We use nested iterations here. For each number in the array, we go through the numbers in the array after it to see if there is a required match. Because there is only one such pair that suits the requirement (add up to a specific target), once we find such a match, we can stop the iteration here.


Problem 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

My solution in Python:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution(object): def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ answer = ListNode(0); pointer = answer; carry = 0; while True: if l1 != None: carry += l1.val; l1 = l1.next; if l2 != None: carry += l2.val; l2 = l2.next; pointer.val = carry % 10; carry /= 10; if l1 != None or l2 != None or carry != 0: pointer.next = ListNode(0); pointer = pointer.next; else: break; return answer;

Review:
Given that the digits are stored in reverse order in the list, the first node in the list is the least significant bit in the integer, so we can add the two lists directly from the first node to the last node. The solution is very straight-forward. Note that along with checking whether both l1 and l2 have reached their ends, we also must check whether the carry bit equals 0. A non-zero carry bit must be carried to the next iteration and have a new node in the answer list to store it. When both l1 and l2 have reached their end, and the carry bit is 0, the algorithm ends.