Regular Expression Matching, Edit Distance, Rotate Image, Spiral Matrix

Regular Expression Matching

Implement regular expression matching with support for ‘.’ and ‘‘.
‘.’ Matches any single character.
‘‘ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a“) → true
isMatch(“aa”, “.“) → true
isMatch(“ab”, “.“) → true
isMatch(“aab”, “ca*b”) → true

Recursive solution

So hard to think of all the cases….

Base case: p was cut to zero
Special Case: p=1, when to return false? (now p!=’‘, this case will be process next
Case 1: p.charAt(1) is not ‘‘,
Case 2: p.charAt(1) is ‘*’,

  public boolean isMatch(String s, String p){
  //base case
  if(p.length()==0) return s.length()==0;
  //p=1 special case
  if(p.length()==1 || p.charAt(1)!='*'){
    //false case: s len=0; 
        /*if the first char of s and the first char of p is not the same, 
        and the char of p is not '.', return false; 
    if(s.length()<1 || p.charAt(0)!=s.charAt(0) && p.charAt(0)!='.')
      return false;
    //otherwise, compare the rest of the string of s and p.
    else return isMatch(s.substring(1),p.substring(1));
  }
  //p!=1 and  when the second char of p is '*'
  else{
    int i=-1;
    while(i<s.length() && (i< 0 || p.charAt(0)=='.' || p.charAt(0)==s.charAt(i))){
      //start from isMatch(s itself, p.substring(2)) stands for 0 preceding element
      //when the '*' stands for 1 or more preceding element,try every possible number
      if(isMatch(s.substring(i+1), p.substring(2)))
        return true;
      i++;}
  }
  return false;
}

---

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

Recursive Solution

public int minDistance(String word1, String word2) {
        if(word1.equals(word2)) return 0;
        if(word1==null || word1.length()<=0) return word2.length();
        if(word2==null || word2.length()<=0) return word1.length();
         
        int delete_dis=minDistance(word1.substring(1),word2)+1;  
        int add_dis=minDistance(word1,word2.substring(1))+1;
        int change_dis=minDistance(word1.substring(1),word2.substring(1)) + word1.charAt(0)==word2.charAt(0) ?  0 : 1;
        
        return Math.min(Math.min(delete_dis, add_dis), change_dis);
    
    }

DP Solution

  public int minDistance(String word1, String word2) {
    if(word2.length()==0) return word1.length();
    if(word1.length()==0) return word2.length();
    int m=word1.length()+1, n=word2.length()+1;
    int[][] Dis=new int[m][n];
    //initiate null cases
    for(int i=0;i<m;i++){Dis[i][0]=i;}
    for(int j=0;j<n;j++){Dis[0][j]=j;}
    //fill up whole table
    for(int i=1; i<m;i++){
        for(int j=1;j<n;j++){
            int del_dis=Dis[i-1][j]+1;
            int add_dis=Dis[i][j-1]+1;
            int change_dis=Dis[i-1][j-1]+ (word1.charAt(i-1)==word2.charAt(j-1)? 0 :1);
            Dis[i][j]=Math.min(Math.min(del_dis,add_dis),change_dis);
        }
    }
    return Dis[m-1][n-1];
    
}

---

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?

Solution

swap four directions layer by layer:

public void rotate(int[][] matrix) {
  
    int len = matrix[0].length;
    for (int layer = 0; layer < len / 2; layer++) {
      for (int i = layer; i < len - 1 - layer; i++) {
        // save upper
        int temp = matrix[layer][i];
     
        // upper = left
        matrix[layer][i] = matrix[len - 1 - i][layer];
        // left = bottom
   
        matrix[len - 1 - i][layer] = matrix[len - 1 - layer][len - 1 - i];
      
        // bottom = right
        matrix[len - 1 - layer][len - 1 - i] = matrix[i][len - 1 - layer];
        // right = up
        matrix[i][len - 1 - layer] = temp;
        
      }
    }
  }

---

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

Solution

public ArrayList<Integer> spiralOrder(int[][] matrix) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if(matrix == null || matrix.length == 0) return result;
    int m = matrix.length;
    int n = matrix[0].length;
    int x=0; 
    int y=0;
    while(m>0 && n>0){
        //if one row/column left, no circle can be formed
        if(m==1){
            for(int i=0; i<n; i++){
                result.add(matrix[x][y++]);
            }
            break;
        }else if(n==1){
            for(int i=0; i<m; i++){
                result.add(matrix[x++][y]);
            }
            break;
        }
        //below, process a circle
        //top - move right
        for(int i=0;i<n-1;i++){
            result.add(matrix[x][y++]);
        }
        //right - move down
        for(int i=0;i<m-1;i++){
            result.add(matrix[x++][y]);
        }
        //bottom - move left
        for(int i=0;i<n-1;i++){
            result.add(matrix[x][y--]);
        }
        //left - move up
        for(int i=0;i<m-1;i++){
            result.add(matrix[x--][y]);
        }
        x++;
        y++;
        m=m-2;
        n=n-2;
    }
    return result;
}