Как бороться с множественностью при проверке подмножества массива
У меня два Arraylist и я хочу проверить, является ли одно подмножеством другого (порядок сравнения не важен). Проблема в том, что: Ar1={e,e,r} а также Ar2={e,r,b,d}, В моем коде это говорит Ar1 это подмножество. Но я хочу сказать, ложь, потому что Ar2 имеет только один e. Как это сделать?
public static void dostuff(String word1,String word2){
List<String> list1 = new ArrayList<String>();
List<String> list2 = new ArrayList<String>();
for (String character : word1.split("")) {
list1.add(character);
}
for (String character : word2.split("")) {
list2.add(character);
}
boolean sub = list1.containsAll(list2) || list2.containsAll(list1);
System.out.println(sub);
}
7 ответов
Я нашел решение сам, пожалуйста, проверьте это правильно, но я верю, что это так.
public static void dostuff(String word1, String word2) {
boolean sub = false;
ArrayList<String> list1 = new ArrayList<String>();
ArrayList<String> list2 = new ArrayList<String>();
ArrayList<String> list3 = new ArrayList<String>();
for (int i = 0; i < word1.length(); i++) {
list1.add(word1.split("")[i]);
}
for (int i = 0; i < word2.length(); i++) {
list2.add(word2.split("")[i]);
}
if (list1.size() >= list2.size()) {
for (String i : list2) {
if (list1.contains(i)) {
list1.remove(i);
list3.add(i);
}
}
if (list2.containsAll(list3) && list2.size() == list3.size()) {
sub = true;
}
} else if (list2.size() > list1.size()) {
for (String i : list1) {
if (list2.contains(i)) {
list2.remove(i);
list3.add(i);
}
if (list1.containsAll(list3) && list1.size() == list3.size()) {
sub = true;
}
}
}
System.out.println(sub);
}
Я думаю, что это может быть то, что вы хотите. Обратите внимание, что list2.remove(elem) возвращается true если элемент был удален, и false если не.
public static boolean dostuff(String word1,String word2){
List<String> list1 = new ArrayList<>();
List<String> list2 = new ArrayList<>();
List<String> list3;
for (String character : word1.split("")) {
list1.add(character);
}
for (String character : word2.split("")) {
list2.add(character);
}
list3 = new ArrayList<>(list2);
boolean isSubset = true;
for (final String elem : list1) {
if (!list2.remove(elem)) {
isSubset = false;
break;
}
}
if (isSubset) {
return true;
}
for (final String elem : list3) {
if (!list1.remove(elem)) {
return false;
}
}
return true;
}
@Johdoe. Приведенная ниже логика может вам помочь. Вы можете оптимизировать, если хотите.
ArrayList<String> list1 = new ArrayList<String>();
ArrayList<String> list2 = new ArrayList<String>();
list1.add("e");
list1.add("a");
list1.add("r");
list2.add("e");
list2.add("r");
list2.add("b");
list2.add("d");
list2.add("a");
System.out.println("list2 " + list2);
System.out.println("list1 " + list1);
Set<Integer> tempList = new HashSet<Integer>();
System.out.println(" containsAll " + list2.containsAll(list1));
for (int i = 0; i < list2.size(); i++) {
for (int j = 0; j < list1.size(); j++) {
if (list2.get(i).equals(list1.get(j))) {
tempList.add(i);
}
}
}
System.out.println(" tempList " + tempList);
System.out.println("list 1 is subset of list 2 "
+ (tempList.size() == list1.size()));
Вот рабочее решение
Проверьте Демо
public static void main (String[] args) throws java.lang.Exception
{
dostuff("eer","erbd");
}
public static void dostuff(String word1, String word2) {
List<String> list1 = new ArrayList<String>();
for (String character : word1.split("")) {
list1.add(character);
}
boolean sub = true;
for (String character : word2.split("")) {
if (list1.remove(character)) {
if (list1.isEmpty()) {
break;
}
} else {
sub = false;
break;
}
}
System.out.println(sub);
}
Вы можете использовать пару карт для хранения частоты каждой буквы:
public static void dostuff(String word1, String word2) {
Map<String, Long> freq1 = Arrays.stream(word1.split("")).collect(
Collectors.groupingBy(Function.identity(), Collectors.counting()));
Map<String, Long> freq2 = Arrays.stream(word2.split("")).collect(
Collectors.groupingBy(Function.identity(), Collectors.counting()));
System.out.println(contains(freq1, freq2) || contains(freq2, freq1));
}
Где contains метод будет следующим:
private static boolean contains(Map<String, Long> freq1, Map<String, Long> freq2) {
return freq1.entrySet().stream().allMatch(
e1 -> e1.getValue().equals(freq2.get(e1.getKey())));
}
Тестовое задание:
dostuff("eer", "erbd"); // {r=1, e=2}, {b=1, r=1, d=1, e=1}, false
dostuff("erbed", "eer"); // {b=1, r=1, d=1, e=2}, {r=1, e=2}, true
Идея состоит в том, чтобы использовать потоки Java 8 для создания карты частот, а затем потоковую передачу набора записей обеих карт для сравнения всех элементов и их частот. Если все записи совпадают, то это означает, что второй список содержит все элементы первого списка с одинаковыми частотами, независимо от порядка.
Если результат false для первого списка проверка выполняется и наоборот, в соответствии с требованиями вопроса.
Теперь, когда я понимаю, что порядок содержимого не имеет значения, вы просто хотите узнать, существуют ли все символы одной строки в другой (с одинаковой частотой) или наоборот.
Попробуйте эту функцию, она проверит все без необходимости вызывать метод дважды и без использования потоков:
public static boolean subsetExists(String s1, String s2) {
String temp = s2.replaceAll(String.format("[^%s]", s1), "");
char[] arr1 = s1.toCharArray();
char[] arr2 = temp.toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
boolean isSubset = new String(arr2).contains(new String(arr1));
if (!isSubset) {
temp = s1.replaceAll(String.format("[^%s]", s2), "");
arr1 = temp.toCharArray();
arr2 = s2.toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
isSubset = new String(arr1).contains(new String(arr2));
}
return isSubset;
}
Вам не нужно беспокоиться, поворачивая Stringс в Lists. Что происходит, мы проверяем, все ли буквы в s1 существуют в s2 или наоборот.
Мы удалили символы, которых нет в s1 от s2 и сохранил этот результат во временном String, Преобразован как временный String а также s1 в char[]s. Затем мы сортируем оба массива и конвертируем их обратно в Strings. Затем мы можем проверить, если NEW SORTED временно Stringcontains() НОВИНКА s1, Если этот результат ложный, то мы применяем ту же логическую проверку из s2 в s1,
Использование:
public static void main(String[] args) throws Exception {
String s1 = "eer";
String s2 = "bderz";
String s3 = "bderzzeee";
System.out.println(subsetExists(s1, s2));
System.out.println(subsetExists(s1, s3));
}
public static boolean subsetExists(String s1, String s2) {
String temp = s2.replaceAll(String.format("[^%s]", s1), "");
char[] arr1 = s1.toCharArray();
char[] arr2 = temp.toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
boolean isSubset = new String(arr2).contains(new String(arr1));
if (!isSubset) {
temp = s1.replaceAll(String.format("[^%s]", s2), "");
arr1 = temp.toCharArray();
arr2 = s2.toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
isSubset = new String(arr1).contains(new String(arr2));
}
return isSubset;
}
Результаты:
false
true
Также обратите внимание, что математический и Java набор уникален, поэтому будьте осторожны с использованием термина "подмножество".
Вы можете использовать карту частот, чтобы проверить, есть ли в одном списке "каждый элемент в другом списке, с тем же или меньшим количеством вхождений". то есть, когда у вас есть список, вы можете преобразовать его в Map<T, Integer> хранить счетчики каждого элемента списка. Использование карты позволяет избежать мутации исходных списков (что вы будете делать, если будете тестировать, удаляя элементы из основного списка по мере их появления):
public static <T> boolean isSublist(List<T> masterList, List<T> subList) {
Map<T, Integer> masterMap = new HashMap<T, Integer>();
for (T t : masterList) masterMap.put(t, 1 + masterMap.getOrDefault(t, 0));
Map<T, Integer> testMap = new HashMap<T, Integer>();
for (T t : subList) testMap.put(t, 1 + testMap.getOrDefault(t, 0));
for(Map.Entry<T, Integer> entry : testMap.entrySet()) {
if (masterMap.getOrDefault(entry.getKey(), 0) < entry.getValue()) return false;
}
return true;
}
getOrDefault доступно только в Java 8, но вы можете легко написать свой собственный метод для выполнения той же операции.