###### tags: `Leetcode` `easy` `array` `hash` `python` `c++`

# 766. Toeplitz Matrix

## [題目連結:] https://leetcode.com/problems/toeplitz-matrix/description/

## 題目:
Given an ```m x n``` ```matrix```, return ```true``` if the matrix is Toeplitz. Otherwise, return ```false```.

A matrix is **Toeplitz** if every diagonal from top-left to bottom-right has the same elements.

**Follow up:**

* What if the ```matrix``` is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
* What if the ```matrix``` is so large that you can only load up a partial row into the memory at once?


## 解題想法:
* 此題為判斷矩陣中每條從左上到右下的值是否相同
* 對於follow up:
* 如果矩陣儲存於硬碟中，且記憶體受到限制，你一次最多只能讀出矩陣中的一行到記憶體中，該怎麼辦？
* 如果矩陣很大，一次只能讀出部分的資料到記憶體中，該怎麼辦？
* 使用hash table即可解決
* 使用字典紀錄:
* key: **row-col**
* val: marix[row][col]
* 逐一判斷
## Python:

class Solution(object):
    def isToeplitzMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: bool
        """
        m=len(matrix)
        n=len(matrix[0])
        dic=collections.defaultdict(int)
        for i in range(m):
            for j in range(n):
                if (i-j) not in dic:
                    dic[i-j]=matrix[i][j]
                else:
                    if matrix[i][j]!=dic[i-j]:
                        return False
        return True

## C++:

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        unordered_map<int,int> dic;
        int m=matrix.size(), n=matrix[0].size();
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                if (dic.find(i-j)==dic.end())
                    dic[i-j]=matrix[i][j];
                else{
                    if (matrix[i][j]!=dic[i-j])
                        return false;
                }
            }
        }
        return true;
    }
};