You are viewing a single comment's thread. Return to all comments →
A top down DP solution:
static int mat[][]; public static boolean canAbbreviate(String a, String b, int n, int m, int[][] mat) { if(m == 0) return true; if(n == 0 && m > 0) return false; if(mat[n][m] != -1) { return mat[n][m] == 1 ? true : false; } if(a.charAt(n-1) == b.charAt(m-1)) { mat[n-1][m-1] = canAbbreviate(a, b, n-1, m-1, mat) == true ? 1 : 0; return mat[n-1][m-1] == 1 ? true : false; } //upperCase n-1 character in string a it and check if equal //recur as in first condition otherwise remove it char c = a.charAt(n-1); String up = c+""; up = up.toUpperCase(); char cu = up.charAt(0); if(cu == b.charAt(m-1)) { mat[n-1][m-1] = canAbbreviate(a, b, n-1, m-1, mat) == true ? 1 : 0; mat[n-1][m] = canAbbreviate(a, b, n-1, m, mat) == true ? 1 : 0; return mat[n-1][m-1] == 1 || mat[n-1][m] == 1 ? true : false; } //check if already is capital then return false String s = c+""; String s2 = c+""; s2 = s2.toLowerCase(); if(!s.equals(s2)) return false; else { //remove it as it is not capital mat[n-1][m] = canAbbreviate(a, b, n-1, m, mat) == true ? 1 : 0; return mat[n-1][m] == 1 ? true: false; } } public static String abbreviation(String a, String b) { // Write your code here if(!isAllCharactersPresent(b.toLowerCase(), a.toLowerCase())) return "NO"; mat = new int[a.length()+1][b.length()+1]; for(int i=0; i < mat.length; i++) { Arrays.fill(mat[i], -1); } return canAbbreviate(a, b, a.length(), b.length(), mat) ? "YES" : "NO"; } public static boolean isAllCharactersPresent(String b, String a){ boolean[] aArr = new boolean[26]; for(char c : a.toCharArray()){ aArr[c - 'a'] = true; } for(char c : b.toCharArray()){ if(aArr[c - 'a'] == false) return false; } return true; }
Abbreviation
You are viewing a single comment's thread. Return to all comments →
A top down DP solution: