class Solution(object):
def hasAlternatingBits(self, n):
"""
:type n: int
:rtype: bool
"""
b = bin(n)[2:]
return all(b[i]!=b[i+1] for i in range(len(b)-1))

class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n, m = len(grid), len(grid[0])
visited = set()
def dfs(i, j, s):
for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
x, y = di+i, dj+j
if x < 0 or y < 0 or x >= n or y >= m:
continue
if grid[x][y] == 0 or (x, y) in visited:
continue
dfs(x, y, s)
ans = 0
for i in xrange(n):
for j in xrange(m):
if grid[i][j] == 1 and (i, j) not in visited:
s = set()
dfs(i, j, s)
ans = max(len(s), ans)
return ans

11
1

11
1
111

111   111
101   110

class Solution(object):
def numDistinctIslands(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def signature(s):
s = sorted(s)
a, b = s[0]
return tuple((i-a, j-b) for i, j in s)

n, m = len(grid), len(grid[0])
visited = set()
def dfs(i, j, s):
for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
x, y = di+i, dj+j
if x < 0 or y < 0 or x >= n or y >= m:
continue
if grid[x][y] == 0 or (x, y) in visited:
continue
dfs(x, y, s)
ans = set()
for i in xrange(n):
for j in xrange(m):
if grid[i][j] == 1 and (i, j) not in visited:
s = set()
dfs(i, j, s)
return len(ans)

c1s1+...+cnsn >= t

min(c[i]+s[i], t[i])

namespace std{
template <>
struct hash<std::vector<int>> {
size_t operator()(const std::vector<int>& v) const {
std::hash<int> hasher;
size_t seed = 0;
for (int i : v) {
seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
return seed;
}
};
}

class Solution {
public:
int minStickers(vector<string>& stickers, string target) {
if (impossible(stickers, target))
return -1;
vector<int> t(26, 0);
for (auto c: target) {
t[c-'a'] ++;
}
unordered_set<vector<int>> ss;
for (auto s: stickers) {
vector<int> tmp(26, 0);
for (auto c: s) tmp[c-'a'] ++;
vector<int> st;
for (int i=0; i<26; i++)
if (t[i] != 0)
st.push_back(min(tmp[i], t[i]));
ss.insert(st);
}
vector<int> tmp;
for (int i=0; i<26; i++)
if (t[i] != 0)
tmp.push_back(t[i]);
t = tmp;

// bfs
tmp = vector<int>(t.size(), 0);
unordered_set<vector<int>> cur, next;
cur.insert(tmp);
int ans = 0;
while (true) {
if (cur.find(t) != cur.end())
return ans;
ans ++;
next.clear();
for (auto c: cur)
for (auto s: ss)
cur = next;
}
}
private:
bool impossible(vector<string>& stickers, string target) {
vector<bool> t(26, false);
for (auto c: target) t[c-'a'] = true;
for (auto s: stickers)
for (auto c: s)
t[c-'a'] = false;
for (auto b: t)
if (b) return true;
return false;
}

vector<int> add(vector<int>& c, vector<int>& s, vector<int>& t) {
vector<int> ans(c.size(), 0);
for (int i=0; i<c.size(); i++)
ans[i] = min(t[i], c[i]+s[i]);
return ans;
}
};