Возврат слов с символами [a, b, b, c] - PullRequest
Новая
       19

Возврат слов с символами [a, b, b, c]

0 голосов
/ 04 августа 2020

Дан список строк ["abc", "abcdb", "gggh", "klsrtabcabc", "118*90", "ggggggggggggggggggggggggggggggggg"]

Возвращает слова, содержащие все буквы из [a,b,b,c]. (Это означает слова, содержащие, по крайней мере, «a» один раз, «b» два раза и 'c' один раз)

Ответ: «abcdb», «klsrtabcab c»

Это алгоритм хэш-карты для этого

  1. Создайте карту частотности символов из списка требуемых символов. Например, для [a,b,b,c] вы получите {a=1, b=2, c=1}

  2. Итерируйте список строк:

  1. Создайте карта частот символов из строки. Например, для «klsrtabcab c» вы получите {a=2, b=2, c=2, k=1, l=1, r=1, s=1, t=1}
  2. Проверьте, есть ли в строке хотя бы необходимое количество символов. Например, поскольку a: 2> = 1, b: 2> = 2 и c: 2> = 1, строка выбирается.
  3. Если выбрано, добавить строку к результату. 3. Верните список результатов.

Я преобразовал первый шаг в код java, как показано ниже, может ли кто-нибудь помочь мне с шагами 2 и 3? 

package JavaInterview;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class practice {
    
  public static void main(String[] args) {

    String str1="abbc";

    //1. Build a character frequency map from the list of required characters.
            
    Map<Character,Integer> hm=new LinkedHashMap<Character,Integer>();
       
    for(Character c : str1.toCharArray()) {
      if(hm.containsKey(c)) {
        hm.put(c, hm.get(c)+1);
      }
                
      else {
        hm.put(c, 1);
      }
    }
  }
}

1 Ответ

1 голос
/ 04 августа 2020

В идеале вам следует попробовать шаги 2 и 3 и обратиться в SO, если вы застряли с проблемой и не можете найти ответ. А пока я дам вам свой подход - просто псевдокод: 

for(int i=0;i<arr.length;i++)
{
     Map<Character,Integer> temp = hm;
     for(Character c : arr[i].toCharArray())
     {
         if(!temp.containsKey(c) or temp[c]<=0)
            break the loop;
         else
            temp[c]--;
     }
     if(end of arr[i] charArray)
            answer.add(arr[i]);
}
...