fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		// your code goes here
  13. 		System.out.println(checkDifference("ray ban women sunglasses","Ray-Ban"));
  14. 	}
  15. 	public static boolean checkDifference(String search_term, String givenBrand) {
  16.         try{
  17.             List<String> allBrands = fetchPossibleBrandVariations(givenBrand);
  18.             System.out.println(allBrands);
  19.             boolean res = false;
  20.             for(String brand : allBrands) {
  21.                 String[] words = search_term.split(" ");
  22.                 String[] brand_words = brand.split(" ");
  23.                 int no_of_words = brand_words.length;
  24.                 for (int i = 0; i <= words.length - no_of_words; i++) {
  25.                     StringBuilder word = new StringBuilder();
  26.                     for (int j = 0; j < no_of_words; j++) {
  27.                         word.append(words[i + j]).append(" ");
  28.                     }
  29.                     if (word.toString().equals(""))
  30.                         continue;
  31.                     int[][] matrix_for_dp = new int[word.length() + 1][brand.length() + 1];
  32.                     for (int j = 0; j < matrix_for_dp.length; j++)
  33.                         Arrays.fill(matrix_for_dp[j], -1);
  34.                     double distance = minDis(word.toString().toLowerCase(), brand.toLowerCase(), word.length(), brand.length(), matrix_for_dp) - 1;
  35.                     double size = brand.length();
  36.                     if (distance / size <= 0.3) {
  37.                         res = true;
  38.                         break;
  39.                     }
  40.                 }
  41.             }
  42.             return res;
  43.         } catch (Exception e){
  44.             return false;
  45.         }
  46.     }
  47.     private static List<String> fetchPossibleBrandVariations(String brand) {
  48.         List<String> allBrands = new ArrayList<>();
  49.         int spaceCount = brand.split(" ").length - 1;
  50.         for(int i=0;i<=spaceCount;i++){
  51.             StringBuilder transformBrand = new StringBuilder();
  52.             int spaces = i;
  53.             for(int j = 0; j< brand.length(); j++){
  54.                 if(brand.charAt(j)==' ' && spaces>0){
  55.                     spaces--;
  56.                 }else{
  57.                     transformBrand.append(brand.charAt(j));
  58.                 }
  59.             }
  60.             allBrands.add(transformBrand.toString());
  61.         }
  62.  
  63.         String possBrand = brand.replace("-"," ");
  64.         allBrands.add(possBrand);
  65.         return allBrands;
  66.     }
  67.     public static int minDis(String s1, String s2, int n, int m,
  68.                              int[][] dp)
  69.     {
  70.         if (n == 0)
  71.             return m;
  72.         if (m == 0)
  73.             return n;
  74.  
  75.         if (dp[n][m] != -1)
  76.             return dp[n][m];
  77.  
  78.         if (s1.charAt(n - 1) == s2.charAt(m - 1)) {
  79.             return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp);
  80.         }
  81.  
  82.         else {
  83.  
  84.             int insert, del, replace;
  85.  
  86.             insert = minDis(s1, s2, n, m - 1, dp);
  87.             del = minDis(s1, s2, n - 1, m, dp);
  88.             replace = minDis(s1, s2, n - 1, m - 1, dp);
  89.             return dp[n][m] = 1 + Math.min(insert, Math.min(del, replace));
  90.         }
  91.     }
  92. }
Success #stdin #stdout 0.09s 47184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[Ray-Ban, Ray Ban]
true
https://ideone.com/ZuRjw5
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!