hcr
BAN USERComplexity: O(n)
public class PalindromicChunk {
private static int call(String s, int count, int lenth, String s2) {
if (s == null || s.isEmpty()) {
return (0);
}
if (s.length() <= 1) {
if (count != 0 && s2.length() - lenth <= 1) {
return (count + 1);
} else {
return (1);
}
}
int n = s.length();
for (int i = 0; i < n / 2; i++) {
if (s.substring(0, i + 1).equals(s.substring(n - 1 - i, n))) {
return call(s.substring(i + 1, n - 1 - i), count + 2, lenth + (i + 1) * 2, s2);
}
}
return count + 1;
}
public static void main(String[] args) {
System.out.println(call(null, 0, 0, null));
System.out.println(call("", 0, 0, ""));
System.out.println(call("V", 0, 0, "V"));
System.out.println(call("VOLVO", 0, 0, "VOLVO"));
System.out.println(call("VOLVOV", 0, 0, "VOLVOV"));
System.out.println(call("ghiabcdefhelloadamhelloabcdefghi", 0, 0, "ghiabcdefhelloadamhelloabcdefghi"));
System.out.println(call("ghiabcdefhelloadamhelloabcdefghik", 0, 0, "ghiabcdefhelloadamhelloabcdefghik"));
System.out.println(call("antaprezatepzapreanta",0,0,"antaprezatepzapreanta"));
}
}
/** Time complexity is O(n) */
import java.util.*;
class TNode {
int val;
ArrayList<TNode> childList;
public TNode(int val, ArrayList<TNode> arrayList) {
this.val = val;
this.childList = arrayList;
}
}
public class DeleteOperationInNArray {
private static TNode construct() {
TNode node = new TNode(Integer.MAX_VALUE, new ArrayList<TNode>());
node.childList.add(new TNode(20, new ArrayList<TNode>()));
TNode n = new TNode(30, new ArrayList<TNode>());
TNode n1 = new TNode(15, null);
n.childList.add(n1);
n1 = new TNode(5, null);
n.childList.add(n1);
n1 = new TNode(6, null);
n.childList.add(n1);
node.childList.get(0).childList.add(n);
n = new TNode(40, new ArrayList<TNode>());
n1 = new TNode(7, null);
n.childList.add(n1);
n1 = new TNode(8, null);
n.childList.add(n1);
n1 = new TNode(9, null);
n.childList.add(n1);
node.childList.get(0).childList.add(n);
n = new TNode(50, new ArrayList<TNode>());
n1 = new TNode(20, null);
n.childList.add(n1);
n1 = new TNode(6, null);
n.childList.add(n1);
n1 = new TNode(8, null);
n.childList.add(n1);
node.childList.get(0).childList.add(n);
return node;
}
private static void delete(TNode head, int val, ArrayList<TNode> result) {
ArrayList<TNode> list = head.childList;
if (list != null) {
for (int i = 0; i < list.size(); i++) {
TNode node = list.get(i);
if (node.val == val) {
if (node.childList != null && !node.childList.isEmpty()) {
head.childList.addAll(node.childList);
}
result.add(node);
head.childList.remove(i);
} else {
delete(node, val, result);
}
}
}
}
public static void main(String[] args) {
TNode head = construct();
int val = 20;// element to be deleted
ArrayList<TNode> result = new ArrayList<TNode>();// holds the result
delete(head, val, result);
for (TNode node : result) {
System.out.print(node.val + " ");
}
}
}
Complexity=len(inputString)*len(dict)*len(wordsinDict) ==> n*m*k O(nmk)
import java.util.HashSet;
import java.util.Set;
import commons.Utils;
public class DictionarymappingDynamic {
static Set<String> dict = new HashSet<String>();
static {
dict.add("ab");
dict.add("abde");
dict.add("abbe");
}
static int getMinimum(String s) {
if (s == null || s.isEmpty()) {
return -1;
}
int max = Integer.MIN_VALUE;
for (String a : dict) {
if (s.length() < a.length()) {
continue;
}
int[][] arr = new int[a.length() + 1][s.length() + 1];
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= s.length(); j++) {
if (a.charAt(i - 1) == s.charAt(j - 1)) {
arr[i][j] = Math.max(arr[i - 1][j - 1] + 1, arr[i - 1][j]);
} else {
arr[i][j] = Math.max(arr[i][j - 1], arr[i - 1][j]);
}
}
}
if (max < arr[a.length()][s.length()]) {
max = arr[a.length()][s.length()];
}
}
return s.length() - max<0?-1:s.length() - max<0;
}
public static void main(String[] args) {
// example string
System.out.println(getMinimum("abbefgj"));
System.out.println(getMinimum(""));
System.out.println(getMinimum("ab"));
System.out.println(getMinimum("a"));
System.out.println(getMinimum("pqrst"));
}
}
Output:
3
-1
0
-1
5
import java.util.*;
public class DictionaryMapping {
static int max = Integer.MIN_VALUE;
static String s = "abbeq";
static Map<String, Boolean> map = new HashMap<String, Boolean>();
static Set<String> set = new HashSet<String>();
public static void main(String[] args) {
set.add("ab");
set.add("abde");
set.add("abbe");
call(0, "");
System.out.println(s.length() - max);
}
private static void call(int m, String str) {
if (map.get(m + "_" + str) != null) {
return;
}
System.out.println(m + " " + str);
if (m >= s.length()) {
return;
}
for (int i = m; i < s.length(); i++) {
if (set.contains(str + s.charAt(i)) && max < (str + s.charAt(i)).length()) {
max = (str + s.charAt(i)).length();
}
map.put(m + "_" + str + s.charAt(i), set.contains(str + s.charAt(i)));
call(i + 1, str + s.charAt(i));
}
}
}
public class RandomGenerate1X1 {
static boolean find(int[][] a) {
int[] row = new int[a.length];
int[] col = new int[a.length];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length; j++) {
if (!increment(a[i][j], row)) {
return false;
}
if (!increment(a[j][i], col)) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int[][] a = { { 1, 2, 1, 1 }, { 2, 1, 4, 2 }, { 1, 2, 4, 1 }, { 3, 2, 2, 2 } };
System.out.println(find(a));
}
private static boolean increment(int m, int[] row) {
if (row[m - 1] == 2) {
return false;
} else {
row[m - 1] += 1;
for (int i = 0; i < row.length; i++) {
if (i != m - 1) {
row[i] = 0;
}
}
}
return true;
}
}
- hcr June 10, 2017