Added new solutions

Мето Трајковски · Мето Трајковски · commit 5c7e1024c9ef · 2019-12-12T00:36:29.000+01:00
diff --git a/Other/palindrome_integer.py b/Other/palindrome_integer.py
@@ -0,0 +1,83 @@
+'''
+Palindrome Integer
+
+Determine whether an integer is a palindrome.
+An integer is a palindrome when it reads the same backward as forward.
+
+Input: 121
+Output: True
+
+Input: -121
+Output: False
+Output explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
+
+Input: 10
+Output: false
+Output oxplanation: Reads 01 from right to left. Therefore it is not a palindrome.
+
+=========================================
+Juste reverse the number and compare it with the original.
+    Time Complexity:    O(N)    , N = number of digits
+    Space Complexity:   O(1)
+If you care about integer overflow (in Python you shouldn't care about this), then reverse only a half of the number
+and compare it with the other half. Also this solution is faster than the previous one because iterates only a half of the number.
+    Time Complexity:    O(N)
+    Space Complexity:   O(1)
+'''
+
+
+##############
+# Solution 1 #
+##############
+
+def palindrome_integer_1(x):
+    if x < 0:
+        return False
+
+    rev = 0
+    temp = x
+    while temp > 0:
+        rev = (rev * 10) + (temp % 10)
+        temp //= 10
+
+    return rev == x
+
+
+##############
+# Solution 2 #
+##############
+
+def palindrome_integer_2(x):
+    # check if negative or ends with zero
+    if (x < 0) or (x > 0 and x % 10 == 0):
+        return False
+
+    rev = 0
+    # if the reversed number is bigger from the original
+    # that means the reversed number has same number of digits or more (1 or 2 more)
+    while x > rev:
+        rev = (rev * 10) + (x % 10)
+        x //= 10
+
+    # first comparison is for even number of digits and the second for odd number of digits
+    return (rev == x) or (rev // 10 == x)
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => True
+print(palindrome_integer_1(121))
+print(palindrome_integer_2(121))
+
+# Test 2
+# Correct result => False
+print(palindrome_integer_1(-121))
+print(palindrome_integer_2(-121))
+
+# Test 2
+# Correct result => False
+print(palindrome_integer_1(10))
+print(palindrome_integer_2(10))
diff --git a/Other/reverse_integer.py b/Other/reverse_integer.py
@@ -0,0 +1,55 @@
+'''
+Reverse Integer
+
+Given signed integer, reverse digits of an integer.
+
+Input: 123
+Output: 321
+
+Input: -123
+Output: -321
+
+Input: 120
+Output: 21
+
+=========================================
+Simple solution, mod 10 to find all digits.
+    Time Complexity:    O(N)    , N = number of digits
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def reverse_integer(x):
+    if x == 0:
+        return 0
+
+    sign = x // abs(x)  # find the sign, -1 or 1
+    x *= sign  # make positive x, or x = abs(x)
+
+    res = 0
+    while x > 0:
+        res = (res * 10) + (x % 10)
+        x //= 10
+
+    return res * sign
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => 321
+print(reverse_integer(123))
+
+# Test 2
+# Correct result => -321
+print(reverse_integer(-123))
+
+# Test 3
+# Correct result => 21
+print(reverse_integer(120))
diff --git a/Strings/anagram_indices.py b/Strings/anagram_indices.py
@@ -1,5 +1,5 @@
 '''
-Anagram indices
+Anagram Indices
 
 Given a word and a string S, find all starting indices in S which are anagrams of word.
 (An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once)
diff --git a/Strings/group_anagrams.py b/Strings/group_anagrams.py
@@ -0,0 +1,61 @@
+'''
+Group Anagrams
+
+Given an array of strings, group anagrams together.
+(An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once)
+
+Input: ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
+Output: [['eat', 'ate', 'tea'], ['tan', 'nat'], ['bat']]
+
+=========================================
+This problem can be solved using a dictionary (hash map), but in order to use a dictinary you'll need to find
+a way to calculate the keys for all strings. This is a same solution but 2 different hash functions.
+
+Sort the letters from the strings, and use the sorted letters as key.
+    Time Complexity:    O(N * KLogK)    , N = number of strings, K = number of characters (chars in the string with most chars)
+    Space Complexity:   O(N)
+Use a letter counter (some kind of counting sort).
+    Time Complexity:    O(N * K)    , O(N * K * 26) = O(N * K), if all of the strings have several chars (less than ~8) the first hash function is better.
+    Space Complexity:   O(N)
+'''
+
+
+############
+# Solution #
+############
+
+def group_anagrams(strs):
+    anagrams = {}
+
+    for st in strs:
+        # or hashable_object = hash_1(st)
+        hashable_object = hash_2(st)
+
+        if hashable_object not in anagrams:
+            anagrams[hashable_object] = []
+        anagrams[hashable_object].append(st)
+
+    return [anagrams[res] for res in anagrams]
+
+def hash_1(st):
+    chars = list(st)
+    chars.sort()
+    # or you can use a string as hash, ''.join(chars)
+    return tuple(chars)
+
+def hash_2(st):
+    all_letters = [0]*26
+    ord_a = 97 # ord('a')
+    for c in st:
+        all_letters[ord(c) - ord_a] += 1
+    # or you can use a string as hash, '<some non-digit character>'.join(all_letters), example: ' '.join(all_letters)
+    return tuple(all_letters)
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => [['eat', 'ate', 'tea'], ['tan', 'nat'], ['bat']]
+print(group_anagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']))
diff --git a/Strings/longest_common_prefix.py b/Strings/longest_common_prefix.py
@@ -0,0 +1,74 @@
+'''
+Longest Common Prefix
+
+Write a function to find the longest common prefix string amongst an array of strings.
+If there is no common prefix, return an empty string ''.
+
+Input: ['flower', 'flow', 'flight']
+Output: 'fl'
+
+Input: ['dog', 'racecar', 'car']
+Output: ''
+
+Input: ['aa', 'a']
+Output: 'a'
+
+=========================================
+Many solutions for this problem exist (Divide and Conquer, Trie, etc) but this is the simplest and the fastest one.
+Use the first string as LCP and iterate the rest in each step compare it with another one.
+    Time Complexity:    O(N*A)  , N = number of strings, A = average chars, or simplest notation O(S) = total number of chars
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def longest_common_prefix(strs):
+    n = len(strs)
+    if n == 0:
+        return ''
+
+    lcp = strs[0]
+    # instead of string manipulations, manipulate with the last common index
+    lcp_idx = len(lcp)
+
+    for i in range(1, n):
+        lcp_idx = min(lcp_idx, len(strs[i]))
+
+        for j in range(lcp_idx):
+            if lcp[j] != strs[i][j]:
+                lcp_idx = j
+                break
+
+    return lcp[:lcp_idx]
+    '''
+    # if you like string manipulations, you can use this code
+    # i don't like string manipulations in Python because they're immutable
+    lcp = strs[0]
+    for i in range(1, n):
+        lcp = lcp[:len(strs[i])]
+        for j in range(len(lcp)):
+            if lcp[j] != strs[i][j]:
+                lcp = lcp[:j]
+                break
+    return lcp
+    '''
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => 'fl'
+print(longest_common_prefix(['flower', 'flow', 'flight']))
+
+# Test 2
+# Correct result => ''
+print(longest_common_prefix(['dog', 'racecar', 'car']))
+
+# Test 3
+# Correct result => 'a'
+print(longest_common_prefix(['aa', 'a']))
diff --git a/Strings/reverse_string.py b/Strings/reverse_string.py
@@ -23,7 +23,7 @@
 ############
 
 def reverse_sentence(sentence):
-    arr = [c for c in sentence]
+    arr = [c for c in sentence] # or just arr = list(sentence)
     start = 0
     end = len(arr) - 1
 
diff --git a/Strings/reverse_vowels.py b/Strings/reverse_vowels.py
@@ -22,7 +22,7 @@
 ############
 
 def reverse_vowels(sentence):
-    arr = [c for c in sentence]
+    arr = [c for c in sentence] # or just arr = list(sentence)
 
     vowels = {
         'a': True, 'A': True,
diff --git a/Strings/reverse_words_in_sentence.py b/Strings/reverse_words_in_sentence.py
@@ -25,7 +25,7 @@
 ############
 
 def reverse_words_in_sentence(sentence):
-    arr = [c for c in sentence]
+    arr = [c for c in sentence] # or just arr = list(sentence)
     n = len(arr)
     last_idx = n - 1
     start = 0
diff --git a/Strings/swap_first_and_last_word.py b/Strings/swap_first_and_last_word.py
@@ -22,7 +22,7 @@
 ############
 
 def swap_first_and_last_word(sentence):
-    arr = [c for c in sentence]
+    arr = [c for c in sentence] # or just arr = list(sentence)
     first_idx = 0
     last_idx = len(arr) - 1
 
