Количество слов в строке

Question

У меня есть специальный случай, когда (сохраняя желаемую временную сложность) Мне нужно подсчитать количество раз, когда слово может быть создано из заданной строки. Мой код ниже управляется только один раз, если слова могут быть созданы более одного раза, это не удается. Есть идеи?

//String that needs to be searched 
String s= "ccoptarra"; 

//Words that need to be found 
String[] words = { "car", "pot", "bag" }; 

ArrayList count = new ArrayList(); 
HashMap map = new HashMap(); 
for (int i = 0; i < words.length; i++) { 
    count.add(0); 
    String w = words[i]; 
    map.put(w, ""); 
    for (int j = 0; j < w.length(); j++) { 
     if (s.contains(String.valueOf(w.charAt(j)))) { 
      map.put(w, map.get(w).toString() + w.charAt(j)); 
      if (map.get(w).equals(w)) 
       count.add(i, ((int)count.get(i)) + 1); 
     } 
    } 
} 
for (int i = 0; i < count.size(); i++) 
    System.out.println("Word: " + words[i] + ", count = " + count.get(i)); 

Выход:

Word: car, count = 1 
Word: pot, count = 1 
Word: bag, count = 0 

Answer 1

Вы можете использовать Карту, чтобы сохранить каждый символ и количество символов. После этого просто проведите тестовые слова и выберите минимальное количество символов из карты для этого слова. Вот код

 //String that needs to be searched 
    String s= "ccoptarra"; 

    //Words that need to be found 
    String[] words = {"car","pot","bag"}; 

    List<Integer> count = new ArrayList<Integer>(); 
    Map<Character, Integer> map = new HashMap<Character, Integer>(); 
    for (int i=0; i<s.length();i++) { 
     char c = s.charAt(i); 
     if (map.get(c) != null) { 
      map.put(c, map.get(c) + 1); 
     } else { 
      map.put(c, 1); 
     } 
    } 

    for (int i=0; i<words.length; i++) { 
     int min = Integer.MAX_VALUE; 
     for (int j=0; j<words[i].length(); j++) { 
      Integer value = map.get(words[i].charAt(j)); 
      if (value == null) { 
       min = 0; 
      } else if (value < min) { 
       min = value; 
      } 
     } 
     count.add(min == Integer.MAX_VALUE ? 0 : min); 
    } 

    for(int i=0; i<count.size(); i++) 
     System.out.println("Word: "+words[i]+", count = "+count.get(i)); 

Answer 2

Я расширить свой воздаем в ответ, чтобы помочь вам получить идею:

Шаг 1: Создайте некоторое отображение для подсчета символов.

Вы можете использовать массив с номером символа в качестве индекса (вычесть значение «a», чтобы сдвинуть смещение на a = 0, b = 1 и т. Д.). Или вы можете использовать Map<Character, Integer>.

Это должно привести к: а = 2, с = 2, а = 1, р = 1, г = 2, т = 1

Шаг 2: Повторите шаг 1 для каждого слова, которое вы ищете , например для автомобиля вы получите a = 1, c = 1, r = 1 (для мешка у вас будет a = 1, b = 1, g = 1).

Шаг 3: для каждого символа в поисковом слове вы вычисляете, как часто вы подбираете требуемое число для символа в доступное число (целую часть фракции) и получаете минимум всех символов в слове ,

Примеры:

• автомобиль: а = 2/1 = 2, с = 2/1 = 2, г = 2/1 = 2 -> минимум 2
• мешок: а = 2/1 = 2, b = 0/1 = 0, g = 0/1 = 0 -> минимум 0