mrincodi
BAN USERboolean isToepliz ( int [][] matrix ){
if ( matrix == null ) return false;
int height = matrix.length;
if ( height == 0 ) return true;
int width = matrix[0].length;
if ( width == 0 ) return true;
for ( int i = height - 1; i >=0; i-- ){
int initialValue = matrix [i][0];
for ( int j = 1; j + i < height && i < width; j++)
if ( matrix [j+i][j] != initialValue )
return false;
}
//Now, the other diagonals.
for ( int i = 1; i < width; i++){
int initialValue = matrix [0][i];
for ( int j = 1; j + i <height && j < width; j++)
if ( matrix [j][i+j] != initialValue) return false;
}
return true;
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class PatternMatching {
ArrayList <String> matchPattern ( String pattern, ArrayList <String> dict){
ArrayList <String> result = new ArrayList <String> ();
for ( String word: dict ){
if ( word.length()==pattern.length()){
HashMap <Character, Character > match = new HashMap <Character, Character > ();
boolean possiblyValid=true;
for ( int i = 0; i < word.length() && possiblyValid; i++ ){
char patternC = pattern.charAt(i);
char c = word.charAt(i);
if ( match.containsKey(c)){
if ( match.get(c)!= patternC)
possiblyValid=false;
}
else
match.put(c,patternC);
}
if (possiblyValid) result.add(word);
}
}
return result;
}
public static void main(String[] args) {
String pattern = "abc";
ArrayList <String> dict = new ArrayList <String> (Arrays.asList("cdf", "too", "hgfdt" ,"paa", "xyz"));
ArrayList <String> matches = new PatternMatching().matchPattern(pattern, dict);
for (String s:matches)
System.out.println(s);
}
}
import java.util.HashMap;
public class ABCs {
HashMap <String, Integer> h = new HashMap <String, Integer> ();
int howManyStrings (int n ){
int total = howManyStrings (n,false,0);
return total;
}
int howManyStrings (int n, Boolean hasBbeenUsed, int trailingCs){
if ( n == 0) return 0;
int total=0;
if (n == 1){
total = 1; //a
if (!hasBbeenUsed) total++; // b
if ( trailingCs < 2 ) total++; // c
return total;
}
else{
//Check if we considered this case already.
String s = n + hasBbeenUsed.toString() + trailingCs;
if ( h.containsKey(s) ) return h.get(s);
total=
howManyStrings (n-1, hasBbeenUsed, 0); //a.
if (!hasBbeenUsed) total+= howManyStrings (n-1, true, 0); //b
if ( trailingCs < 2) total+= howManyStrings (n-1, hasBbeenUsed, trailingCs++); //Final c.
h.put (s, total);
return total;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a = new ABCs().howManyStrings (20);
System.out.println(a);
}
}
I don't understand why you say the "Bleed" code is a BFS when it's a DFS. In a BFS you use a queue. Here you're just using basic recursion (with memoization), so it's a DFS.
- mrincodi July 13, 2018