Ke Xu kanrourou
kanrourou
/ Regular Expression Matching NFA.java
Created
November 5, 2014 07:43
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| private class Graph { | |
| private int V; | |
| private int E; | |
| private ArrayList<Integer>[] adj; | |
| private boolean[] visited; | |
| public Graph(int V) { |
kanrourou
/ Wildcard Matching backtracking + pruning.java
Created
November 5, 2014 23:47
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| public boolean isMatch(String s, String p) { | |
| int len1 = p.length(); | |
| int len2 = s.length(); | |
| int iStore = 0, jStore = 0, i = 0, j = 0; | |
| boolean hasStar = false; | |
| if (len1 == 0) | |
| return len2 == 0; | |
| while (j < len2) { | |
| if (i < len1 && (p.charAt(i) == s.charAt(j) || p.charAt(i) == '?')) { |
kanrourou
/ Wildcard Matching DP.java
Last active
August 29, 2015 14:08
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| public boolean isMatch(String s, String p) { | |
| //filter the last test case | |
| if(s.length()>300 && p.charAt(0)=='*' && p.charAt(p.length()-1)=='*') | |
| return false; | |
| int len1 = p.length(); | |
| int len2 = s.length(); | |
| boolean[][] arr = new boolean[len1 + 1][len2 + 1]; | |
| arr[0][0] = true; | |
| for (int i = 0; i < len1; i++) { |
kanrourou
/ word break.java
Created
November 6, 2014 05:44
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| public boolean wordBreak(String s, Set<String> dict) { | |
| int len = s.length(); | |
| if(len == 0) | |
| return dict.contains(s); | |
| boolean[] record = new boolean[len]; | |
| for(int i = 0; i < len; ++i){ | |
| if(dict.contains(s.substring(0,i + 1))){ | |
| record[i] = true; | |
| continue; |
kanrourou
/ word search.java
Created
November 6, 2014 05:47
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| public boolean exist(char[][] board, String word) { | |
| int len = word.length(); | |
| if(len == 0) | |
| return false; | |
| int rows = board.length; | |
| int cols = board[0].length; | |
| boolean[][] visited = new boolean[rows][cols]; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| private class Pair{ | |
| private int first; | |
| private int second; | |
| public Pair(int a, int b) { | |
| first = a; | |
| second = b; |
kanrourou
/ edit distance.java
Created
November 6, 2014 07:54
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| private int min (int a, int b, int c) { | |
| if (a <= b && a <= c) | |
| return a; | |
| else if (b <=a && b <= c) | |
| return b; | |
| else | |
| return c; | |
| } |
kanrourou
/ single Number III.java
Created
November 10, 2014 23:34
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| int singleNumber(int A[]) { | |
| int ones = 0, twos = 0, threes = 0, fours = 0; | |
| for(int i = 0; i < A.length; i++){ | |
| threes ^= (A[i] & ones & twos); | |
| twos ^= (A[i] & ones); | |
| ones = (ones ^ A[i]) & ~fours; | |
| fours = fours ^ (A[i] & ~ones & ~twos & ~threes); |
kanrourou
/ reverse words in a string.java
Created
December 20, 2014 23:51
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| public String reverseWords(String s) { | |
| if (s == null) | |
| return ""; | |
| String res = ""; | |
| int len = s.length(); | |
| for (int i = 0; i < len;) { | |
| String temp = ""; | |
| while (i < len && s.charAt(i) == ' ') | |
| i++; |
kanrourou
/ Evaluate Reverse Polish Notation.java
Created
December 21, 2014 01:18
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| public int evalRPN(String[] tokens) { | |
| if (tokens == null) | |
| return 0; | |
| Stack<Integer> stack = new Stack<Integer>(); | |
| int len = tokens.length; | |
| for (int i = 0; i < len; i++) { | |
| String str = tokens[i]; | |
| if (isOperator(str)) { |