/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
{
// your code goes here
System.
out.
println(checkDifference
("ray ban women sunglasses",
"Ray-Ban")); }
public static boolean checkDifference
(String search_term,
String givenBrand
) { try{
List<String> allBrands = fetchPossibleBrandVariations(givenBrand);
System.
out.
println(allBrands
); boolean res = false;
for(String brand
: allBrands
) { String[] words
= search_term.
split(" "); String[] brand_words
= brand.
split(" "); int no_of_words = brand_words.length;
for (int i = 0; i <= words.length - no_of_words; i++) {
StringBuilder word = new StringBuilder();
for (int j = 0; j < no_of_words; j++) {
word.append(words[i + j]).append(" ");
}
if (word.toString().equals(""))
continue;
int[][] matrix_for_dp = new int[word.length() + 1][brand.length() + 1];
for (int j = 0; j < matrix_for_dp.length; j++)
Arrays.
fill(matrix_for_dp
[j
],
-1); double distance = minDis(word.toString().toLowerCase(), brand.toLowerCase(), word.length(), brand.length(), matrix_for_dp) - 1;
double size = brand.length();
if (distance / size <= 0.3) {
res = true;
break;
}
}
}
return res;
return false;
}
}
private static List
<String
> fetchPossibleBrandVariations
(String brand
) { List<String> allBrands = new ArrayList<>();
int spaceCount = brand.split(" ").length - 1;
for(int i=0;i<=spaceCount;i++){
StringBuilder transformBrand = new StringBuilder();
int spaces = i;
for(int j = 0; j< brand.length(); j++){
if(brand.charAt(j)==' ' && spaces>0){
spaces--;
}else{
transformBrand.append(brand.charAt(j));
}
}
allBrands.add(transformBrand.toString());
}
String possBrand
= brand.
replace("-",
" "); allBrands.add(possBrand);
return allBrands;
}
public static int minDis
(String s1,
String s2,
int n,
int m,
int[][] dp)
{
if (n == 0)
return m;
if (m == 0)
return n;
if (dp[n][m] != -1)
return dp[n][m];
if (s1.charAt(n - 1) == s2.charAt(m - 1)) {
return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp);
}
else {
int insert, del, replace;
insert = minDis(s1, s2, n, m - 1, dp);
del = minDis(s1, s2, n - 1, m, dp);
replace = minDis(s1, s2, n - 1, m - 1, dp);
return dp
[n
][m
] = 1 + Math.
min(insert,
Math.
min(del, replace
)); }
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCQlTeXN0ZW0ub3V0LnByaW50bG4oY2hlY2tEaWZmZXJlbmNlKCJyYXkgYmFuIHdvbWVuIHN1bmdsYXNzZXMiLCJSYXktQmFuIikpOwoJfQoJcHVibGljIHN0YXRpYyBib29sZWFuIGNoZWNrRGlmZmVyZW5jZShTdHJpbmcgc2VhcmNoX3Rlcm0sIFN0cmluZyBnaXZlbkJyYW5kKSB7CiAgICAgICAgdHJ5ewogICAgICAgICAgICBMaXN0PFN0cmluZz4gYWxsQnJhbmRzID0gZmV0Y2hQb3NzaWJsZUJyYW5kVmFyaWF0aW9ucyhnaXZlbkJyYW5kKTsKICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKGFsbEJyYW5kcyk7CiAgICAgICAgICAgIGJvb2xlYW4gcmVzID0gZmFsc2U7CiAgICAgICAgICAgIGZvcihTdHJpbmcgYnJhbmQgOiBhbGxCcmFuZHMpIHsKICAgICAgICAgICAgICAgIFN0cmluZ1tdIHdvcmRzID0gc2VhcmNoX3Rlcm0uc3BsaXQoIiAiKTsKICAgICAgICAgICAgICAgIFN0cmluZ1tdIGJyYW5kX3dvcmRzID0gYnJhbmQuc3BsaXQoIiAiKTsKICAgICAgICAgICAgICAgIGludCBub19vZl93b3JkcyA9IGJyYW5kX3dvcmRzLmxlbmd0aDsKICAgICAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IHdvcmRzLmxlbmd0aCAtIG5vX29mX3dvcmRzOyBpKyspIHsKICAgICAgICAgICAgICAgICAgICBTdHJpbmdCdWlsZGVyIHdvcmQgPSBuZXcgU3RyaW5nQnVpbGRlcigpOwogICAgICAgICAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbm9fb2Zfd29yZHM7IGorKykgewogICAgICAgICAgICAgICAgICAgICAgICB3b3JkLmFwcGVuZCh3b3Jkc1tpICsgal0pLmFwcGVuZCgiICIpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBpZiAod29yZC50b1N0cmluZygpLmVxdWFscygiIikpCiAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgIGludFtdW10gbWF0cml4X2Zvcl9kcCA9IG5ldyBpbnRbd29yZC5sZW5ndGgoKSArIDFdW2JyYW5kLmxlbmd0aCgpICsgMV07CiAgICAgICAgICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBtYXRyaXhfZm9yX2RwLmxlbmd0aDsgaisrKQogICAgICAgICAgICAgICAgICAgICAgICBBcnJheXMuZmlsbChtYXRyaXhfZm9yX2RwW2pdLCAtMSk7CiAgICAgICAgICAgICAgICAgICAgZG91YmxlIGRpc3RhbmNlID0gbWluRGlzKHdvcmQudG9TdHJpbmcoKS50b0xvd2VyQ2FzZSgpLCBicmFuZC50b0xvd2VyQ2FzZSgpLCB3b3JkLmxlbmd0aCgpLCBicmFuZC5sZW5ndGgoKSwgbWF0cml4X2Zvcl9kcCkgLSAxOwogICAgICAgICAgICAgICAgICAgIGRvdWJsZSBzaXplID0gYnJhbmQubGVuZ3RoKCk7CiAgICAgICAgICAgICAgICAgICAgaWYgKGRpc3RhbmNlIC8gc2l6ZSA8PSAwLjMpIHsKICAgICAgICAgICAgICAgICAgICAgICAgcmVzID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIHJldHVybiByZXM7CiAgICAgICAgfSBjYXRjaCAoRXhjZXB0aW9uIGUpewogICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgICAgfQogICAgfQogICAgcHJpdmF0ZSBzdGF0aWMgTGlzdDxTdHJpbmc+IGZldGNoUG9zc2libGVCcmFuZFZhcmlhdGlvbnMoU3RyaW5nIGJyYW5kKSB7CiAgICAgICAgTGlzdDxTdHJpbmc+IGFsbEJyYW5kcyA9IG5ldyBBcnJheUxpc3Q8PigpOwogICAgICAgIGludCBzcGFjZUNvdW50ID0gYnJhbmQuc3BsaXQoIiAiKS5sZW5ndGggLSAxOwogICAgICAgIGZvcihpbnQgaT0wO2k8PXNwYWNlQ291bnQ7aSsrKXsKICAgICAgICAgICAgU3RyaW5nQnVpbGRlciB0cmFuc2Zvcm1CcmFuZCA9IG5ldyBTdHJpbmdCdWlsZGVyKCk7CiAgICAgICAgICAgIGludCBzcGFjZXMgPSBpOwogICAgICAgICAgICBmb3IoaW50IGogPSAwOyBqPCBicmFuZC5sZW5ndGgoKTsgaisrKXsKICAgICAgICAgICAgICAgIGlmKGJyYW5kLmNoYXJBdChqKT09JyAnICYmIHNwYWNlcz4wKXsKICAgICAgICAgICAgICAgICAgICBzcGFjZXMtLTsKICAgICAgICAgICAgICAgIH1lbHNlewogICAgICAgICAgICAgICAgICAgIHRyYW5zZm9ybUJyYW5kLmFwcGVuZChicmFuZC5jaGFyQXQoaikpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGFsbEJyYW5kcy5hZGQodHJhbnNmb3JtQnJhbmQudG9TdHJpbmcoKSk7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIFN0cmluZyBwb3NzQnJhbmQgPSBicmFuZC5yZXBsYWNlKCItIiwiICIpOwogICAgICAgIGFsbEJyYW5kcy5hZGQocG9zc0JyYW5kKTsKICAgICAgICByZXR1cm4gYWxsQnJhbmRzOwogICAgfQogICAgcHVibGljIHN0YXRpYyBpbnQgbWluRGlzKFN0cmluZyBzMSwgU3RyaW5nIHMyLCBpbnQgbiwgaW50IG0sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW50W11bXSBkcCkKICAgIHsKICAgICAgICBpZiAobiA9PSAwKQogICAgICAgICAgICByZXR1cm4gbTsKICAgICAgICBpZiAobSA9PSAwKQogICAgICAgICAgICByZXR1cm4gbjsKCiAgICAgICAgaWYgKGRwW25dW21dICE9IC0xKQogICAgICAgICAgICByZXR1cm4gZHBbbl1bbV07CgogICAgICAgIGlmIChzMS5jaGFyQXQobiAtIDEpID09IHMyLmNoYXJBdChtIC0gMSkpIHsKICAgICAgICAgICAgcmV0dXJuIGRwW25dW21dID0gbWluRGlzKHMxLCBzMiwgbiAtIDEsIG0gLSAxLCBkcCk7CiAgICAgICAgfQoKICAgICAgICBlbHNlIHsKCiAgICAgICAgICAgIGludCBpbnNlcnQsIGRlbCwgcmVwbGFjZTsKCiAgICAgICAgICAgIGluc2VydCA9IG1pbkRpcyhzMSwgczIsIG4sIG0gLSAxLCBkcCk7CiAgICAgICAgICAgIGRlbCA9IG1pbkRpcyhzMSwgczIsIG4gLSAxLCBtLCBkcCk7CiAgICAgICAgICAgIHJlcGxhY2UgPSBtaW5EaXMoczEsIHMyLCBuIC0gMSwgbSAtIDEsIGRwKTsKICAgICAgICAgICAgcmV0dXJuIGRwW25dW21dID0gMSArIE1hdGgubWluKGluc2VydCwgTWF0aC5taW4oZGVsLCByZXBsYWNlKSk7CiAgICAgICAgfQogICAgfQp9