165 Compare Version Numbers

Compare two version numbers version1 and version1.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int pos1=0;
        int pos2=0;
        int token1=getToken(version1,pos1);
        int token2=getToken(version2,pos2);
        while((pos1<version1.size() || pos2<version2.size()) && token1==token2)
        {   
            token1=getToken(version1,pos1);
            token2=getToken(version2,pos2);
        }
        if (token1==token2)
            return 0;
        if (token1>token2)
            return 1;
        return -1;
    }
    int getToken(string &version,int &pos)
    {
        if (pos>=version.size())
            return 0;
        int res=0;
        while(pos<version.size() && version[pos]!='.')
        {
            res = res*10+version[pos]-'0';
            pos++;
        }
        if (version[pos]=='.')
            pos++;
        return res;
    }
};

139 Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        if (s.size()<=0 || dict.size()<=0)
            return false;
        vector<bool> res = vector<bool>(s.size(),false);
        
        if (dict.find(s.substr(0,1))!=dict.end())
            res[0]=true;
        for (int i=1;i<s.size();i++)
        {
            if (dict.find(s.substr(0,i+1))!=dict.end())
            {
                res[i]=true;
                continue;
            }
            for (int k=0;k<i;k++)
            {
                if (res[k]== true && dict.find(s.substr(k+1,i-k))!=dict.end())
                {
                    res[i]=true;
                    break;
                }
            }
        }
        return res[s.size()-1];
        
    }
};

140 Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution: Backtracking and avoid unnecessary checking

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        if (s.size()<=0 || dict.size()<=0)
            return res;
        vector<string> solution;
        vector<bool> possible = vector<bool>(s.size()+1,true);
        help(s,dict,0,s.size()-1,possible,solution,res);
        
        return res;
    }
    void help(string s,unordered_set<string> &dict,int start,int end,vector<bool> &possible,vector<string>&solution,vector<string>&res)
    {
        if (start>end)
        {
            string str;
            for (int i=0;i<solution.size();i++)
            {
                str+=(solution[i]+' ');
            }
            str.pop_back();
            res.push_back(str);
            return;
        }
        for (int i=start;i<=end;i++)
        {
            string tmp = s.substr(start,i-start+1);
            if (dict.find(tmp)!=dict.end() && possible[i+1])
            {
                solution.push_back(tmp);
                int before = res.size();
                help(s,dict,i+1,end,possible,solution,res);
                if (res.size()==before)
                    possible[i+1]= false;
                solution.pop_back();
            }
        }
    }
};

91 Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

class Solution {
public:
    int numDecodings(string s) {
        if (s.size()<=0)
            return 0;
        int first = 0;
        int second = 1;
        int res=0;

        for (int i=0;i<s.size();i++)
        {
            res=0;
            if (isValid(s[i]))
                res=second;
            if (i-1>=0 && isValid(s[i-1],s[i]))
                res+= first;
            first = second;
            second = res;
        }
        return res;
    }
    bool isValid(char a)
    {
        if (a>='1' && a<='9')
            return true;
        return false;
    }
    bool isValid(char a,char b)
    {
        if (a=='0')
            return false;
        int res = (a-'0')*10+b-'0';
        if (res>=1 && res<=26)
            return true;
        return false;
    }
};

48 Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        if (matrix.size()<=1)
            return;
        int n = matrix.size();
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<n-i;j++)
            {
                swap(matrix[i][j],matrix[n-1-j][n-1-i]);
            }
        }
        for (int i=0;i<n/2;i++)
        {
            for (int j=0;j<n;j++)
                swap(matrix[i][j],matrix[n-1-i][j]);
        }
    }
};

54 Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> res;
        int m= matrix.size();
        if (m<=0)
            return res;
        int n = matrix[0].size();
        if (n<=0)
            return res;
            
        int left = 0,right = n-1;
        int up=0,down=m-1;
        while(left<=right && up<=down)
        {
            for (int j=left;j<=right;j++)
            {
                res.push_back(matrix[up][j]);
            }
            up++;
            for (int i=up;i<=down;i++)
            {
                res.push_back(matrix[i][right]);
            }
            right--;
            if (up<=down)
            {
                for (int j=right;j>=left;j--)
                {
                    res.push_back(matrix[down][j]);
                }
            }
            down--;
            if (left<=right)
            {
                for (int i=down;i>=up;i--)
                {
                    res.push_back(matrix[i][left]);
                }
            }
            left++;
        }
        return res;
    }
};

58 Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, 
Given s = "Hello World",
return 5.

class Solution {
public:
    int lengthOfLastWord(const char *s) {
        if (strlen(s)<=0)
            return 0;
        int pos = strlen(s)-1;
        int count=0;
        for (;pos>=0;pos--)
        {
            if (s[pos]==' ')
            {
                if (count==0)   
                    continue;
                return count;
            }
            else
            {
                count++;
            }
        }
        return count;
    }
};

38 Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

class Solution {
public:
    string countAndSay(int n) {
        if (n<=0)
            return "";
        string res = "1";
        string res2;
        for (int i=2;i<=n;i++)
        {
            int val = res[0];
            int count = 1;
            for (int j=1;j<res.size();j++)
            {
                if (res[j]==res[j-1])
                {
                    count++;
                }
                else
                {
                    res2.push_back(count+'0');
                    res2.push_back(val);
                    val = res[j];
                    count=1;
                }
            }
            res2.push_back(count+'0');
            res2.push_back(val);
            res = res2;
            res2="";
        }
        
        return res;
    }
};

72 Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<int> level = vector<int>(word2.size()+1,0);
        vector<vector<int>> res = vector<vector<int>>(word1.size()+1,level);
        for (int j=1;j<=word2.size();j++)
            res[0][j]=j;
        for (int i=1;i<word1.size()+1;i++)
        {
            res[i][0]=i;
            for (int j=1;j<word2.size()+1;j++)
            {
                if (word1[i-1]==word2[j-1])
                {
                    res[i][j]=res[i-1][j-1];
                }
                else
                {
                    res[i][j]=min_val(res[i-1][j],res[i][j-1],res[i-1][j-1])+1;
                }
            }
        }
        return res[word1.size()][word2.size()];
    }
    int min_val(int a,int b,int c)
    {
        int d = a<b?a:b;
        return d<c? d:c;
    }
};

166 Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0)
            return "";
        if (numerator == 0)
            return "0";
        bool negative = false;
        long a = numerator;
        long b = denominator;
        if (a<0) 
        {   
            negative = !negative;
            a = abs(a);
        }
        if (b<0) 
        {
            negative = !negative;
            b = abs(b);
        }
        
        string res = help(a,b);
        if (negative)
            res.insert(res.begin(),'-');
        return res;
    }
    string help(long numerator,long denominator)
    {
        string res;
        long integer = numerator/denominator;
        res+= int2str(integer);
        numerator %= denominator;
        if (numerator!=0)
            res+= '.';
        int pos=res.size();
        bool loop = false;
        unordered_map<int,int> mp;
        while(numerator!=0)
        {
            if (mp.find(numerator)==mp.end())
                mp[numerator]=pos;
            else
            {
                pos = mp[numerator];
                loop = true;
                break;
            }
            numerator *=10;
            res+= numerator/denominator +'0';
            numerator %= denominator;
            pos++;
        }
        if (loop)
        {
            res.insert(res.begin()+pos,'(');
            res+= ')';
        }
        return res;
    }
    string int2str(long a)
    {
        if (a==0)
            return "0";
        string res;
        while(a>0)
        {
            char c = a%10 + '0';
            res.insert(res.begin(),c);
            a /=10;
        }
        return res;
    }
};

76 Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

class Solution {
public:
    string minWindow(string S, string T) {
        string res;
        if (S.size()<=0 || T.size()<=0 || S.size()<T.size())
            return res;
        unordered_map<char,int> ht;
        for (int i=0;i<T.size();i++)
        {
            ht[T[i]]++;
        }
        int fast=0;
        int slow = 0;
        int max_window = INT_MAX;
        int charCount=0;
        for (;fast<S.size();fast++)
        {
            if (ht.find(S[fast])==ht.end())
                continue;
            if (ht[S[fast]]>0)
            {
                ht[S[fast]]--;
                charCount++;
            }
            else
            {
                ht[S[fast]]--;
            }
            if (charCount>=T.size())
            {
                while(slow<=fast-T.size())
                {
                    if(ht.find(S[slow])==ht.end())
                        slow++;
                    else if (ht[S[slow]]<0)
                    {
                        ht[S[slow]]++;
                        slow++;
                    }
                    else
                        break;
                }
                int current_window = fast-slow+1;
                if (current_window<max_window)
                {
                    max_window = current_window;
                    res = S.substr(slow,max_window);
                }
            }
        }
        return res;
    }
};

30 Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        vector<int> res;
        if (L.size()<=0)
            return res;
        int wordCount = L.size();
        int wordSize = L[0].size();
        if (S.size() < wordCount*wordSize)
            return res;
        unordered_map<string, int> mp, mp_copy;
        for (int i=0;i<L.size();i++)
        {
            mp_copy[L[i]]++;
        }
        for (int start=0;start<=S.size()-wordCount*wordSize; ++start)
        {
            mp=mp_copy;
            bool exist = true;
            for (int j=0;j<wordCount;j++)
            {
                string cur = S.substr(start+j*wordSize, wordSize);
                if (mp.find(cur)==mp.end() || mp[cur]<=0)
                {
                    exist = false;
                    break;
                }
                else
                {
                    mp[cur]--;
                }
            }
            if (exist)
            {
                res.push_back(start);
            }
        }
        return res;
    }
    
};

49 Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        vector<string> res;
        unordered_map<string, vector<string>> hmap;
        for (int i=0;i<strs.size();i++)
        {
            string temp = strs[i];
            sort(temp.begin(),temp.end());
            hmap[temp].push_back(strs[i]);
        }
        for (auto it = hmap.begin();it!=hmap.end();it++)
        {
            if (it->second.size()>1)
            {
                for (int j=0;j<it->second.size();j++)
                    res.push_back(it->second[j]);
            }
        }
        return res;
        
    }
};

119 Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

class Solution {
public:
    vector getRow(int rowIndex) {
        vector res=vector(rowIndex+1,1);
        for (int i=2;i<=rowIndex;i++)
        {
            for (int j=i-1;j>0;j--)
            {
                res[j]=res[j]+res[j-1];
            }
        }
        return res;
    }
};

79 Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        vector<bool> line = vector<bool>(board[0].size(),false);
        vector<vector<bool>> visited = vector<vector<bool>>(board.size(),line);
        if (word.size()<=0)
            return true;
        for (int i=0;i<board.size();i++)
        {
            for (int j=0;j<board[0].size();++j)
            {
                if (board[i][j]==word[0])
                {
                    if (dfs(board,visited,word,1,i,j))
                        return true;
                }
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>> &board, vector<vector<bool>>& visited, string word, int pos, int i,int j)
    {
        if (pos>=word.size())
            return true;
        visited[i][j] = true;
        if (i>=1 && board[i-1][j]==word[pos] && !visited[i-1][j] && dfs(board,visited,word,pos+1,i-1,j))
            return true;
        if (i+1<board.size() && board[i+1][j]==word[pos] && !visited[i+1][j] && dfs(board,visited,word,pos+1,i+1,j))
            return true;
        if (j>=1 && board[i][j-1]==word[pos] && !visited[i][j-1] && dfs(board,visited,word,pos+1,i,j-1))
            return true;
        if (j+1<board[0].size() && board[i][j+1]==word[pos] && !visited[i][j+1] && dfs(board,visited,word,pos+1,i,j+1))
            return true;
        visited[i][j]=false;
        return false;
    }
};

131 Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<string> partition;
        vector<vector<string>> res;
        help(s,0,partition,res);
        return res;
    }
    void help(string s, int start_pos,vector<string> &partition, vector<vector<string>> &res)
    {
        if (start_pos>=s.size())
        {
            res.push_back(partition);
            return;
        }
        for (int end_pos = start_pos;end_pos<s.size();end_pos++)
        {
            if (isPalindrome(s,start_pos,end_pos))
            {
                partition.push_back(s.substr(start_pos,end_pos-start_pos+1));
                help(s,end_pos+1,partition,res);
                partition.pop_back();
            }
        }
    }
    bool isPalindrome(string s, int start_pos, int end_pos)
    {
        if (start_pos>=end_pos)
            return true;
        if (s[start_pos]!=s[end_pos])
            return false;
        return isPalindrome(s,start_pos+1,end_pos-1);
    }
};

22 Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string comb;
        vector<string> res;
        if (n<=0)
            return res;
        help(n,comb,res,0,0);
        return res;
    }
    void help(int n, string & comb, vector<string> &res, int leftCount, int rightCount)
    {
        if (leftCount==n && rightCount ==n)
        {
            res.push_back(comb);
            return;
        }
        if (leftCount<n)
        {
            comb.push_back('(');
            help(n,comb,res,leftCount+1,rightCount);
            comb.pop_back();
        }
        if (rightCount<leftCount)
        {
            comb.push_back(')');
            help(n,comb,res,leftCount,rightCount+1);
            comb.pop_back();
        }
    }
};

60 Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> number;
        int factorial = 1;
        for (int i=1;i<=n;i++)
        {
            number.push_back(i);
            factorial *= i;
        }
        k--;
        for (int i=0;i<n;i++)
        {
            factorial = factorial/(n-i);
            int k_bit = k/factorial;
            forward(number,i+k_bit,i);
            k=k%factorial;
        }
        
        string res;
        for (int i=0;i<number.size();i++)
            res.push_back(number[i]+'0');
        return res;
    }
    void forward(vector<int> &number, int new_pos,int old_pos)
    {
        for (int j=new_pos;j>old_pos;j--)
        {
            swap(number[j],number[j-1]);
        }
    }
};

51 N-Queens

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively. For example, There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string>> strRes;
        if (n<=0)
            return strRes;
        vector<int> res = vector<int>(n,0);
        help(n,res,0,strRes);
        return strRes;
    }
    void help(int n,vector<int>& res,int i,vector<vector<string>> &strRes)
    {
        if (i>=n)
            return store(res,strRes);
        for (int j=0;j<n;j++)
        {
            if (isValid(res,i,j))
            {
                res[i]=j;
                help(n,res,i+1,strRes);
                res[i]=0;
            }
        }
    }
    bool isValid(vector<int>& res,int i,int j)
    {
        for (int k=0;k<i;k++)
        {
            if (res[k]==j || abs(res[k]-j)==(i-k))
                return false;
        }
        return true;
    }
    void store(vector<int>& res,vector<vector<string>>& strRes)
    {
        int n = res.size();
        string level(n,'.');
        vector<string> emptyMatrix = vector<string>(n,level);
        for (int i=0;i<n;i++)
        {
            emptyMatrix[i][res[i]]='Q';
        }
        strRes.push_back(emptyMatrix);
    }
    
};

147. Insertion Sort List

Sort a linked list using insertion sort.

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (!head || !head->next)
            return head;
        ListNode *dummy = new ListNode(INT_MIN);
        dummy->next = head;
        ListNode *current = head;
        while(current && current->next)
        {
            if (current->next->val>current->val)
            {
                current = current->next;
                continue;
            }
            ListNode* tmp= current->next;
            current->next = current->next->next;
            ListNode* search = dummy;
            while(search->next && search->next->val < tmp->val)
            {
                search = search->next;
            }
            tmp->next = search->next;
            search->next = tmp;
        }
        head = dummy->next;
        delete dummy;
        return head;
        
    }
};

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution:
step[n]=step[n-1]+step[n-2], Fibonacci sequence
Dynamic programming or iterations

class Solution {
public:
    int climbStairs(int n) {
        if (n<=1)
            return n;
        if (n==2)
            return 2;
        int first = 1;
        int second = 2;
        int res = 0;
        for (int i=3;i<=n;i++)
        {
            res = first+second;
            first = second;
            second = res;
        }
        return res;
    }
};

130 Surrounded Regions

Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if (board.size()<=1 || board[0].size()<=1)
            return;
        for (int j=0;j<board[0].size();j++)
        {
            if (board[0][j]=='O')
            {
                board[0][j]='Y';
                check(board,0,j);
            }
        }
        for (int j=0;j<board[0].size();j++)
        {
            if (board[board.size()-1][j]=='O')
            {
                board[board.size()-1][j]='Y';
                check(board,board.size()-1,j);
            }
        }
        for (int i=1;i<board.size()-1;i++)
        {
            if (board[i][0]=='O')
            {
                board[i][0]='Y';
                check(board,i,0);
            }
        }
        for (int i=1;i<board.size()-1;i++)
        {
            if (board[i][board[0].size()-1]=='O')
            {
                board[i][board[0].size()-1]='Y';
                check(board,i,board[0].size()-1);
            }
        }
        
        for (int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if (board[i][j]=='Y')
                    board[i][j]='O';
                else if (board[i][j]=='O')
                    board[i][j]='X';
            }
        }
    }
    void check(vector<vector<char>> &board,int i,int j)
    {
        if (i-1>0 && board[i-1][j]=='O')
        {
            board[i-1][j]='Y';
            check(board,i-1,j);
        }
        if (i+1<board.size() && board[i+1][j]=='O')
        {
            board[i+1][j]='Y';
            check(board,i+1,j);
        }
        if (j-1>0 && board[i][j-1]=='O')
        {
            board[i][j-1]='Y';
            check(board,i,j-1);
        }
        if (j+1<board[0].size() &&board[i][j+1]=='O')
        {
            board[i][j+1]='Y';
            check(board,i,j+1);
        }
    }
};

133 Clone Graph

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node)
            return NULL;
        unordered_map<int,UndirectedGraphNode*> mp;
        return help(node,mp);
    }
    UndirectedGraphNode* help(UndirectedGraphNode *node,unordered_map<int,UndirectedGraphNode*> &mp)
    {
        if (mp.find(node->label)==mp.end())
        {
            UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
            mp[node->label]=newNode;
            for (int i=0;i<node->neighbors.size();i++){
                newNode->neighbors.push_back(help(node->neighbors[i],mp));
            }
        }
        return mp[node->label];
    }
};