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;
    }