Leetcode: Substring with Concatenation of All Words in Java

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).

Solution:
public ArrayList<Integer> findSubstring(String S, String[] L) {
        HashMap<String, Integer> Lmap = new HashMap<String, Integer>();
        HashMap<String, Integer> Smap = new HashMap<String, Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        int total = L.length;
        if(total==0)
        return result;
        for(int i=0;i<total;i++)
        {
            if(!Lmap.containsKey(L[i]))
            Lmap.put(L[i], 1);
            else
            {
                int k = Lmap.get(L[i]);
                Lmap.put(L[i], k+1);
            }
        }
        int len = L[0].length();
        for(int i=0;i<=S.length()-len*total;i++)
        {
            Smap.clear();
            int j = 0;
            for(;j<total;j++)
            {
                String s = S.substring(i+j*len, i+(j+1)*len);
                if(!Lmap.containsKey(s))
                    break;
                if(!Smap.containsKey(s))
                Smap.put(s, 1);
                else
                {
                    int k = Smap.get(s);
                    Smap.put(s, k+1);
                }
                if(Smap.get(s)>Lmap.get(s))
                    break;
            }
            if(j==total)
            {
                result.add(i);
            }
        }
        return result;
    }

Leetcode: Next Permutation in Java

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1


Solution:
public void nextPermutation(int[] num) {
        int size = num.length-1;
        if(size<=0)
            return;
        int nonorder = 0;
        int tmp = 0;
        while(size>0&&num[size]<=num[size-1])
        {
            size--;
        }
        nonorder = size;
        if(nonorder>0)
        {
            nonorder--;
            size = num.length-1;
            while(size>=0&&num[size]<=num[nonorder])
            {
                size--;
            }
            tmp = num[size];
            num[size] = num[nonorder];
            num[nonorder] = tmp;
            nonorder++;
        }
        size =  num.length-1;
        while(nonorder<size)
        {
            tmp = num[size];
            num[size] = num[nonorder];
            num[nonorder] = tmp;
            nonorder++;
            size--;
        }
    }

Leetcode: Implement strStr() in C++

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Solution:
char *strStr(char *haystack, char *needle) {
        int lenA = strlen(haystack);
        int lenB = strlen(needle);
        if(lenA>=0&&lenB==0)
        return haystack;
        if(lenA==0)
        return NULL;
        vector<int> next(lenB, 0);
        next[0] = -1;
        int cur = 0;
        int k =-1;
        while(cur<lenB-1)
        {
            if(k==-1||needle[cur]==needle[k])
            {
                cur++;
                k++;
                next[cur] = k;
            }
            else
                k = next[k];
        }
        k = -1;
        int curA = 0;
        int curB = 0;
        while(curA<lenA)
        {
            if(curB==-1||haystack[curA]==needle[curB])
            {
                curA++;
                curB++;
            }
            else
                curB = next[curB];
            if(curB == lenB)
                return &haystack[curA-curB];
        }
        return NULL;
    }

Leetcode: Valid Sudoku in C++

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Solution:
bool isValidSudoku(vector<vector<char> > &board) {
        vector<int> row(9, 0);
        vector<int> column(9, 0);
        vector<int> row1 = row;
        vector<int> column1 = column;
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    if(row[board[i][j]-49]!=0)
                       return false;
                     else
                       row[board[i][j]-49] = 1;
                }
                if(board[j][i]!='.')
                {
                    if(column[board[j][i]-49]!=0)
                       return false;
                     else
                       column[board[j][i]-49] = 1;
                }
            }
            row = row1;
            column = column1;
        }
        for(int i=0;i<9;i+=3)
        {
            for(int j=0;j<9;j+=3)
            {
                for(int m=0;m<3;m++)
                {
                    for(int n=0;n<3;n++)
                    {
                        if(board[m+i][n+j]!='.')
                        {
                           if(row[board[m+i][n+j]-49]!=0)
                             return false;
                           else
                             row[board[m+i][n+j]-49] = 1;
                        }
                    }
                }
                row = row1;
            }
        }
        return true;
    }

Leetcode: Spiral Matrix in C++

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].

Solution:
void spiral_input(vector<vector<int>> s,int lx,int ly,int m,int n, vector<int>& result)
    {
    if(m<=0||n<=0)
return;
for(int i=0;i<n;i++)
result.push_back(s[lx][ly+i]);
for(int i=1;i<m;i++)
result.push_back(s[lx+i][ly+n-1]);
    if(m!=1)
    {
        for(int i=n-2;i>=0;i--)
    result.push_back(s[lx+m-1][ly+i]);
    }
if(n!=1)
    {
        for(int i=m-2;i>=1;i--)
    result.push_back(s[lx+i][ly]);
    }
spiral_input(s,lx+1,ly+1,m-2,n-2, result);
    }
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> result;
        if(matrix.size()==0)
        return result;
        spiral_input(matrix,0,0,matrix.size(),matrix[0].size(),result);
        
    }

Leetcode: Letter Combinations of a Phone Number in C++

Given a digit string, return all possible letter combinations that the number could represent.
Solution:
vector<char> switchchar(char input)
    {
    vector<char> result;
switch(input)
{
case '2':
result.push_back('a');
result.push_back('b');
result.push_back('c');
break;
case '3':
result.push_back('d');
result.push_back('e');
result.push_back('f');
break;
case '4':
result.push_back('g');
result.push_back('h');
result.push_back('i');
break;
case '5':
result.push_back('j');
result.push_back('k');
result.push_back('l');
break;
case '6':
result.push_back('m');
result.push_back('n');
result.push_back('o');
break;
case '7':
result.push_back('p');
result.push_back('q');
result.push_back('r');
result.push_back('s');
break;
case '8':
result.push_back('t');
result.push_back('u');
result.push_back('v');
break;
case '9':
result.push_back('w');
result.push_back('x');
result.push_back('y');
result.push_back('z');
break;
   }
   return result;
    }
    void helper(string digits, string cur, int num, vector<string>& result )
    {
        if(num==digits.size())
        {
            result.push_back(cur);
        }
        char digit = digits[num];
        vector<char> option = switchchar(digit);
        for(int i=0;i<option.size();i++)
        {
            helper(digits, cur+option[i], num+1, result);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        string cur = "";
        helper(digits, cur, 0, result);
        return result;
    }

Leetcode: Anagrams in Java

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

Note: All inputs will be in lower-case.

Solution:
public ArrayList<String> anagrams(String[] strs) {
        int len = strs.length;
        HashMap<String, Integer> mymap = new HashMap<String, Integer>();
        ArrayList<String> result = new ArrayList<String>();
        for(int i=0;i<len;i++)
        {
            char[] cur = strs[i].toCharArray();
            Arrays.sort(cur);
            String sorted = new String(cur);
            if(mymap.containsKey(sorted))
            {
                if(mymap.get(sorted)!=-1)
                {
                    result.add(strs[mymap.get(sorted)]);
                    mymap.put(sorted,-1);
                }
                result.add(strs[i]);
            }
            else
            {
                mymap.put(sorted, i);
            }
        }
        return result;
    }

Leetcode: Maximum Subarray in C++

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.
More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution:
int maxSubArray(int A[], int n) {
        int cur = 0;
        int max = INT_MIN;
        for(int i=0;i<n;i++)
        {
            if(cur>=0)
            {
                cur+=A[i];
            }
            else
                cur = A[i];
            if(cur>max)
            max = cur;
        }
        return max;
    }

Leetcode: Word Ladder in C++

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time

1. Each intermediate word must exist in the dictionary

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
return its length 5.

• Return 0 if there is no such transformation sequence.

• All words have the same length.

• All words contain only lowercase alphabetic characters.

For example,

Given:

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",

Note:

Solution: BFS
int ladderLength(string start, string end, unordered_set<string> &dict) {
        if(start.size()!=end.size())
            return 0;
        queue<string> cur;
        queue<string> next;
        cur.push(start);
        int distance =1;
        while(!cur.empty()&&dict.size()>0)
        {
            while(!cur.empty())
            {
                string tmp = cur.front();
                cur.pop();
                for(int i=0;i<tmp.size();i++)
                {
                    char k = tmp[i];
                    for(char m='a';m<='z';m++)
                    {
                        if(m==k)
                        continue;
                        tmp[i] = m;
                        if(tmp == end)
                        return distance+1;
                        if(dict.count(tmp)>0)
                        {
                            next.push(tmp);
                            dict.erase(tmp);
                        }
                        tmp[i] = k;
                    }
                }
            }
            swap(cur, next);
            distance++;
        }
        return 0;
    }

Leetcode: Insert Interval in C++

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Solution:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> result;
        int len = intervals.size();
        int cur = 0;
        while(cur<len&&intervals[cur].end<newInterval.start)
        {
            result.push_back(intervals[cur]);
            cur++;
        }
        while(cur<len&&intervals[cur].start<=newInterval.end)
        {
            newInterval.start = min(intervals[cur].start, newInterval.start);
            newInterval.end = max(intervals[cur].end, newInterval.end);
            cur++;
        }
        result.push_back(newInterval);
        while(cur<len)
        {
            result.push_back(intervals[cur]);
            cur++;
        }
        return result;
    }

Leetcode: Search a 2D Matrix in C++

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.

• The first integer of each row is greater than the last integer of the previous row.

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

For example,

Consider the following matrix:

Given target = 3, return true.

Solution:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
         if(matrix.size()==0)
         return false;
         int row = matrix.size();
         int column = matrix[0].size();
         int start = 0;
         int end = row-1;
         int mid = 0;
         while(start<=end)
         {
            mid = start+(end-start)/2;
            if(matrix[mid][0]>target)
            {
                end = mid-1;
            }
            else if(matrix[mid][0]<target)
            {
                start = mid+1;
            }
            else
                return true;
         }
         if(end<0)
         return false;
         int cur = end;
         start = 0;
         end = column-1;
         while(start<=end)
         {
            mid = start+(end-start)/2;
            if(matrix[cur][mid]>target)
            {
                end = mid-1;
            }
            else if(matrix[cur][mid]<target)
            {
                start = mid+1;
            }
            else
                return true;
         }
         return false;
    }

Leetcode: Search Insert Position in C++

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0


Solution:
int searchInsert(int A[], int n, int target) {
        int start = 0;
        int end = n-1;
        int mid = 0;
        while(start<=end)
        {
            mid = start+(end-start)/2;
            if(A[mid]>target)
            {
                end = mid-1;
            }
            else if(A[mid]<target)
            {
                start = mid+1;
            }
            else
                return mid;
        }
        return start;
    }

Leetcode: Minimum Path Sum in C++

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.Solution：

First Version:void helper(vector<vector<int> > &grid, int m, int n, int& max, int cur)    {        if(m<=grid.size()-1&&n<=grid[0].size()-1)        {            cur+=grid[m][n];            if(m==grid.size()-1&&n==grid[0].size()-1&&cur<max)            max = cur;            helper(grid, m, n+1, max, cur);            helper(grid, m+1, n, max,cur);        }        else            return;    }    int minPathSum(vector<vector<int> > &grid) {        int max = INT_MAX;        if(grid.size()==0)        return 0;        int cur = 0;        helper(grid, 0,0,max,cur);        return max;    }

Second Version:

int minPathSum(vector<vector<int> > &grid) {
        if(grid.size()==0)
        return 0;
        int row = grid.size();
        int column = grid[0].size();
        vector<int> cur(column, INT_MAX);
        cur[0] = 0;
        for(int i=0;i<row;i++)
        {
            cur[0] = cur[0]+grid[i][0];
            for(int j=1;j<column;j++)
            {
                cur[j] = min(cur[j], cur[j-1])+grid[i][j];
            }
        }
        return cur[column-1];
    }

Leetcode: Permutation Sequence in C++

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"

1. "132"

1. "213"

1. "231"

1. "312"

1. "321"

Given n and k, return the k^th permutation sequence.

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

Solution:
string getPermutation(int n, int k) {
        string result;
        vector<int> num(n);
        int total = 1;
        for(int i=0;i<n;i++)
        {
            num[i] = i+1;
            total *= i+1;
        }
        int q;
        for(int i=n;i>=1;i--)
        {
            total = total/i;
            q = (k-1)/total;
            k = k - q*total;
            result+='0'+num[q];
            num.erase(num.begin()+q);
        }
        return result;
    }