---
# System prepended metadata

title: 1. Arrays & Hashing (9) - Python
tags: [working]

---

# 1. Arrays & Hashing (9) - Python

> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
> 
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)

<!-- 常用色碼紀錄
Easy:   <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard:   <font color="#ee2f56">**Hard**</font>
-->

* Hash
    * 廣義概念，將任意長度的輸入值轉換為固定長度的輸出值，此過程稱為 hashing
    * 輸出後的數值又稱為 hash value(雜湊值)
* Hash function
    * 進行 hashing 時，將輸入映射到固定長度輸出的函數。
    * 通常在加密領域會用到
    * 在 hash table 或 hash set 等資料結構中，用來計算元素儲存的位置
* Hash table
    * 一種資料結構，以鍵值對(key-value pair)的形式儲存資料
    * hash table 中的每個 key 都是唯一的
    * 通過 hash function 將 key 映射到表格中的某個對應位置
    * Python 中的 dictionary 就是 hash table 實作
    * 用來實現高效率的查找與插入
* Hash set
    * 一種根據 hash table 所建立的資料結構，用來儲存不重複的元素集合
    * 不在意元素的順序與鍵值對的關係
    * Python 中的 set 就是 hash set 的實作

## 1. Contains Duplicate
<font color="#00ad5f">**Easy**</font>

> Given an integer array `nums`, return `True` if any value appears **more than once** in the array, otherwise return `False`

### Example 1:
```java
Input: nums = [1, 2, 3, 3]
Output: True
```

### Example 2:
```java
Input: nums = [1, 2, 3, 4]
Output: False
```

### Recommended complexity

* Time complexity: $O(n)$
    * where n is the size of the input array
* Space complexity: $O(n)$

### Solution

**(1) Brute force**

#### 1. Brute force
```python=
class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False
```

#### 2. Sort
```python=
class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return True
        return False
```

#### 3. Hash set
```python=
class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        hash_set = set()

        for i in nums:
            if i in hash_set:
                return True
            else:
                hash_set.add(i)
        return False
```

## 2. Is Anagram
<font color="#00ad5f">**Easy**</font>

> Given two strings `s` and `t`, return `True` if the two strings are anagrams of each other, otherwise return `False`
> 
> An **anagram** is a string that contains the exact same characters as another string, but the order of the characters can be different.

### Example 1:
```java
Input: s = "racecar", t = "carrace"
Output: Ture
```

### Example 2:
```java
Input: s = "jar", t = "jam"
Output: False
```

### Constraints
* `s` and `t` consist of lowercase English letters.

###
### Solution

#### 1. Sorting
```python=
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s = sorted(s)
        t = sorted(t)
        
        if len(s) != len (t):
            return False
        
        for i in range(len(s)):
            if s[i] == t[i]:
                continue
            else:
                return False
        return True
```

#### 2. Hash table
```python=
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        dict_s = dict()
        dict_t = dict()
        
        for i in range(len(s)):
            if s[i] in dict_s:
                dict_s[s[i]] += 1
            else:
                dict_s[s[i]] = 0
            
            if t[i] in dict_t:
                dict_t[t[i]] += 1
            else:
                dict_t[t[i]] = 0
        
        if dict_s == dict_t:
            return True
        else:
            return False
```

## 3. Two Integer Sum
<font color="#00ad5f">**Easy**</font>

> Given an array of integers `nums` and an integer `target`, return the indices `i` and `j` such that `nums[i] + nums[j] == target` and `i != j`.
> 
> You may assume that every input has exactly one pair of indices `i` and `j` that satisfy the condition.
> 
> Return the answer with the smaller index first.

### Example 1:
```java
Input: nums = [3, 4, 5, 6], target = 7
Output: [0,1]
```

### Example 2:
```java
Input: nums = [5, 5], taeget = 10
Output: [0, 2]
```

### Example 3:
```java
Input: nums = [5, 5], target = 10
Output: [0, 1]
```

### Constraints
* `2 <= nums.length <= 1000`
* `-10,000,000 <= nums[i] <= 10,000,000`
* `-10,000,000 <= target <= 10,000,000`

### Solution
#### 1. Brute force
```python=
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
```

## 4. Encode and Decode Strings

<font color="#ffbb00">**Medium**</font>

> Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.
> 
> Please implement `encode` and `decode`

### Example 1:

```java
Input: ["neet","code","love","you"]

Output:["neet","code","love","you"]
```

### Example 2:

```java
Input: ["we","say",":","yes"]

Output: ["we","say",":","yes"]
```

### Constraints

* `0 <= strs.length < 100`
* `0 <= strs[i].length < 200`
* `strs[i]` contains only UTF-8 characters.

以下程式碼**測資成功但提交失敗**。因為 while 迴圈中儲存每個字串的長度時，只儲存第一個數字(`num = int(s[i])`)，如果某個字串有 9 個字元以上就會出錯，例如: 

### Solution
#### 1. My (False)
* `["neet","code","love","you"]` 編碼後為 `"4#neet4#code4#love4#you"`，可以正確解碼
* `["ThisIsProblem", "ha"]` 編碼後為 `13#ThisIsProblem2#ha` 無法正確解碼，因為第一個字串的長度只會讀取到 `1` 而不是 `13`

```python=
class Solution:

    def encode(self, strs: List[str]) -> str:
        encode = ""
        for s in strs:
            encode += f"{len(s)}#{s}"
        
        return encode

    def decode(self, s: str) -> List[str]:
        decode = []
        i = 0

        while (i < len(s)):
            num = int(s[i]) # problem is here !!
            decode.append(s[i+2:i+2+num])
            i += (2+num)
        
        return decode
```

### 2. Correct version

```python=
class Solution:

    def encode(self, strs: List[str]) -> str:
        encode = ""
        for s in strs:
            encode += f"{len(s)}#{s}"
        
        return encode

    def decode(self, s: str) -> List[str]:
        decode = []
        i = 0

        while (i < len(s)):
            j = i
            while (s[j] != "#"):
                j += 1
            length = int(s[i:j])
            i = j + 1
            decode.append(s[i:i+length])
            i = i + length
        return decode
```

## 5. Product of Array Except Self

<font color="#ffbb00">**Medium**</font>

> Given an integer array `nums`m return an array `output` where `output[i]` is the product of all the elements of `nums` except `nums[i]`.
> 
> Each product is **guaranteed** to fit in a **32-bit** integer.
> 
> Follow-up: Could you solve it in $O(n)$ time without using the division operation ?

### Example 1:

```java
Input: nums = [1, 2, 4, 6]
Output: [48, 24, 12, 8]
```

### Example 2:

```java
Input: nums = [-1, 0, 1, 2, 3]
Output: [0, -6, 0, 0, 0]
```

### Constraints

* `2 <= nums.length <= 1000`
* `20 <= nums[i] <= 20`

### Solution
#### 1. My (Division ver.)

* 有使用除法進行運算
* 時間複雜度為: $O(n^2)$

```python=
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        product = 1
        for item in nums:
            product *= item
        
        output = []
        for i in range(len(nums)):
            if nums[i] != 0:
                res = product // nums[i]
                output.append(res)
            else:
                res = 1
                for j in range(len(nums)):
                    if j == i:
                        pass
                    else:
                        res *= nums[j]
                output.append(res)
        return output
```

#### 2. Correct (Non-division ver.)

* 注意迴圈不能針對串列的元素迭代，應該要迭代 `range()`，否則如果串列有相同元素就會出錯
* 時間複雜度為: $O(n^2)$
```python=
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = []
        for i in range(len(nums)):
            product = 1
            for j in range(len(nums)):
                if j == i:
                    pass
                else:
                    product *= nums[j]
            res.append(product)
        
        return res
```

#### 3. Correct (Prefix & postfix)

* 時間複雜度 $O(n)$
* 空間複雜度 $O(n)$，因為使用兩個 array 來儲存 prefix 與 postfix

```python=
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        pre = [1] * len(nums)
        post = [1] * len(nums)
        for i in range(len(nums)):
            if i == 0:
                pre[i] = nums[i]
                post[-1-i] = nums[-1-i]
            else:
                pre[i] = pre[i-1] * nums[i]
                post[-1-i] = post[-i] * nums[-1-i]
        
        res = []
        for i in range(len(nums)):
            if i == 0:
                res.append(post[i+1])
            elif i == (len(nums)-1):
                res.append(pre[i-1])
            else:
                res.append(pre[i-1] * post[i+1])
        
        return res
```

* 時間複雜度 $O(n)$
* 空間複雜度 $O(n)$

```pytohn=
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left_default = right_default = 1
        n = len(nums)
        res = [1] * n

        # prefix produt
        for i in range(1, n):
            res[i] = res[i] * nums[i-1] * left_default
            left_default *= nums[i-1]
        # postfix product
        for i in range(1, n):
            res[-1-i] = res[-1-i] * nums[-i] * right_default
            right_default *= nums[-i]
        
        return res
```

## 6. Valid Sudoku
<font color="#ffbb00">**Medium**</font>

> You are given a `9 x 9` Sudoku board `board`. A Sudoku board is valid of the following rules are followed:
> 1. Each row must contain the digits `1-9` without duplicates.
> 2. Each column must contain the digits `1-9` without duplicates.
> 3. Each of the nine `3x3` sub-boxes of the grid must contain the digits `1-9` without duplicates.
> 
> Return `True` if the Sudoku board is valid, otherwise return `False` 
> Note: A board does not need to be full or be solvable to be valid.

### Example 1:

![image](https://hackmd.io/_uploads/H15JvMMWke.png)

```java
Input: board = 
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","8",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]

Output: true

```

### Example 2:

```java
Input: board = 
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","1",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]

Output: false
```

### Constraints
* `board.length == 9`
* `board[i].length == 9`
* `board[i][j]` is a digit `1-9` or `"."`.

### Solution
#### 1. Brute force
```python=
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Brute force solution

        # search row
        for row in range(9):
            numbers = set()
            for idx in range(9):
                if board[row][idx] == ".":
                    continue
                if board[row][idx] in numbers:
                    return False
                else:
                    numbers.add(board[row][idx])
        
        # search column
        for col in range(9):
            numbers = set()
            for idx in range(9):
                if board[idx][col] == ".":
                    continue
                if board[idx][col] in numbers:
                    return False
                else:
                    numbers.add(board[idx][col])
        
        # search sub-boxes
        for box in range(9):
            numbers = set()
            for i in range(3):
                for j in range(3):
                    row = (box // 3) * 3 + i
                    col = (box % 3) * 3 + j
                    if board[row][col] == ".":
                        continue
                    if board[row][col] in numbers:
                        return False
                    else:
                        numbers.add(board[row][col])
        return True
```

#### 2. Hash set
```python=
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Hash set
        rows = defaultdict(set)
        cols = defaultdict(set)
        squares = defaultdict(set)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if ((board[r][c] in rows[r]) or \
                    (board[r][c] in cols[c]) or \
                    (board[r][c] in squares[(r//3, c//3)])):
                    return False
                else:
                    rows[r].add(board[r][c])
                    cols[c].add(board[r][c])
                    squares[(r//3, c//3)].add(board[r][c])
        return True
```
## . Longest Conseccutive Sequence
<font color="#ffbb00">**Medium**</font>

> Given an array of integers `nums`, return the length of the longest consecutive seauence of elements.
> 
> A consecutive sequence is a sequence of elements in which each element is exactly `1` greater than the previous element.
> 
> You must write an algorithm that runs in $O(n)$ time.

### Example 1:
```java
Input: nums = [2, 20, 4, 10, 3, 4, 5]
Output: 4
```
 The longest consecutive sequence is `[2, 3, 4, 5]`
 
### Example 2:
 ```java
 Input: nums = [0, 3, 2, 5, 4, 6, 1, 1]
 Output: 7
 ```
 
### Constraints
 * `0 <= nums.length <= 1000`
 * `-10^9 <= nums[i] <= 10^9`

### Solution
#### 1. My version

結合了 sorted 與 hash set 的概念
```python=
# My version

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        HashSet = set(nums)
        HashSet_sort = sorted(HashSet)
        length = []
        count = 1
        for i in range(len(HashSet_sort)-1):
            if list(HashSet_sort)[i+1] - list(HashSet_sort)[i] == 1:
                count += 1
            else:
                length.append(count)
                count = 1
        length.append(count)

        return max(length)
```

##### 2. 
