How to deal with plurality when checking if an arralist is a subset
I have two Arraylist
and I want to check if it is a subset of the other (ordering does not matter in comparison). The problem is this: let's say Ar1={e,e,r}
and Ar2={e,r,b,d}
. My code says it Ar1
is a subset of. But I want it to say false, the reason Ar2
only has one e. How to do it?
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);
}
source to share
I found the solution myself, please check it correctly, but I believe it is.
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);
}
source to share
I think this might be what you want. Note that it list2.remove(elem)
returns true
if the item was removed and false
if not.
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;
}
source to share
Here is a working solution
Check Demo
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);
}
source to share
Also note that the math and java set are unique, so be careful about using the term "subset".
You can use a frequency map to check if one list has “every item in another list with the same or fewer occurrences”. those. after you have your list, you can convert it to Map<T, Integer>
to store the counts of each list item. Using a map avoids changing the original lists (which you might have done if testing was removed from the master list when you came across them):
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
only available since Java 8, but you can easily write your own method to take care of the same operation.
source to share
@Johdoe. This logic can help you. you can optimize if you like.
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()));
source to share
Now that I understand that the order of the content doesn't matter, you just want to know if all the characters of one string exist in another (with the same frequency) or vice versa.
Try this function, it will check everything without calling the method twice and without using threads:
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;
}
You don't have to worry about turning yours String
into List
s. What happens is we check if all letters exist in s1
in s2
or vice versa.
We have removed characters that are not in s1
from s2
and saved them in a temporary one String
. It transformed as temporary String
, and s1
in char[]
s. We then sort both arrays and convert them back to String
s. Then we can check whether there is a NEW SORTED temporary String
contains()
NEW Sort s1
. If this result is false, we apply the same boolean check from s2
to s1
.
Using:
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;
}
Results:
false
true
source to share
You can use a couple of cards to store the frequency of each letter:
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));
}
If the method contains
is as follows:
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())));
}
Test:
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
The idea is to use java 8 streams to create a frequency map and then pass the data stream of both maps to compare all the elements and their frequencies. If all records match, then this means that the second list contains all the elements of the first list with the same frequencies, regardless of order.
If there is a result for the first list false
, the check is also performed the other way around, in accordance with the requirements for the request.
source to share