مساله:
دو رشته S1, S2 به شما داده می شود، ما می خواهیم تفاوت دو رشته را مشاهده کنیم. ما فقط حروف کوچک را در نظر می گیریم(a to z). ابتدا فرکانس هر یک از حروف کوچک را در s1 و s2 بشماریم.
s1 = “A aaaa bb c”
s2 = “& aaa bbb c d”
s1 has 4 ‘a’, 2 ‘b’, 1 ‘c’
s2 has 3 ‘a’, 3 ‘b’, 1 ‘c’, 1 ‘d’
بنابراین حداکثر تکرار ‘a’ در رشته های s1 , s2 عدد ۴ است که در رشته s1 هم قرار دارد. بیشترین تعداد ‘b’ در رشته s2 و به اندازه ۳ است. در ادامه ما حروفی را که حداکثر تعداد آنها کمتر یا مساوی 1 باشد را در نظر نمی گیریم.
ما می توانیم تفاوت های رشته های s1 و s2 را در رشته زیر در نظر بگیریم:
“1: aaaa/2: bbb” که در آن 1 در 1: aaaa مخفف رشته s1 و aaaa است زیرا حداکثر تعداد a برابر ۴ است. به همین ترتیب 2: bbb مخفف رشته s2 و bbb است زیرا حداکثر تعداد b برابر ۳ است.
وظیفه ما این است که رشته ای تولید کنیم که هر حروف کوچک در s1 و s2 به شرطی که بیش از یک بار تکرار شده باشند و بیشترین تکرار را داشته باشند را نمایش بدهیم. نمایش به این گونه است که تعداد حرف قبل از جمله باید نمایش داده شود و اگر تعداد حداکثر در s1 باشد با نماد :. و اگر در s2 باشد با نماد =: نمایش داده می شود.
در نتیجه ، زیر رشته ها (یک زیر رشته به عنوان مثال 2: nnnnn یا 1: hhh ؛ شامل پیشوند است) مرتب سازی به صورت کاهشی از طول آنها و هنگامی که طول یکسانی داشتن به ترتیب صعودی از حروف مرتب شود (حروف و ارقام – بیشتر دقیقاً بر اساس نقطه کد مرتب شده است) ؛ گروه های مختلف با ‘/’ جدا می شوند. نمونه ها را ببینید.
امیدوارم نمونه های دیگر بتوانند این موضوع را واضح تر نشان دهند.
s1 = "my&friend&Paul has heavy hats! &" s2 = "my friend John has many many friends &" mix(s1, s2) --> "2:nnnnn/1:aaaa/1:hhh/2:mmm/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss" s1 = "mmmmm m nnnnn y&friend&Paul has heavy hats! &" s2 = "my frie n d Joh n has ma n y ma n y frie n ds n&" mix(s1, s2) --> "1:mmmmmm/=:nnnnnn/1:aaaa/1:hhh/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss" s1="Are the kids at home? aaaaa fffff" s2="Yes they are here! aaaaa fffff" mix(s1, s2) --> "=:aaaaaa/2:eeeee/=:fffff/1:tt/2:rr/=:hh"
Description:
Given two strings s1 and s2, we want to visualize how different the two strings are. We will only take into account the lowercase letters (a to z). First let us count the frequency of each lowercase letters in s1 and s2.
s1 = “A aaaa bb c”
s2 = “& aaa bbb c d”
s1 has 4 ‘a’, 2 ‘b’, 1 ‘c’
s2 has 3 ‘a’, 3 ‘b’, 1 ‘c’, 1 ‘d’
So the maximum for ‘a’ in s1 and s2 is 4 from s1; the maximum for ‘b’ is 3 from s2. In the following we will not consider letters when the maximum of their occurrences is less than or equal to 1.
We can resume the differences between s1 and s2 in the following string: “1:aaaa/2:bbb” where 1 in 1:aaaa stands for string s1 and aaaa because the maximum for a is 4. In the same manner 2:bbb stands for string s2 and bbb because the maximum for b is 3.
The task is to produce a string in which each lowercase letters of s1 or s2 appears as many times as its maximum if this maximum is strictly greater than 1; these letters will be prefixed by the number of the string where they appear with their maximum value and :. If the maximum is in s1 as well as in s2 the prefix is =:.
In the result, substrings (a substring is for example 2:nnnnn or 1:hhh; it contains the prefix) will be in decreasing order of their length and when they have the same length sorted in ascending lexicographic order (letters and digits – more precisely sorted by codepoint); the different groups will be separated by ‘/’. See examples and “Example Tests”.
Hopefully other examples can make this clearer.
s1 = "my&friend&Paul has heavy hats! &" s2 = "my friend John has many many friends &" mix(s1, s2) --> "2:nnnnn/1:aaaa/1:hhh/2:mmm/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss" s1 = "mmmmm m nnnnn y&friend&Paul has heavy hats! &" s2 = "my frie n d Joh n has ma n y ma n y frie n ds n&" mix(s1, s2) --> "1:mmmmmm/=:nnnnnn/1:aaaa/1:hhh/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss" s1="Are the kids at home? aaaaa fffff" s2="Yes they are here! aaaaa fffff" mix(s1, s2) --> "=:aaaaaa/2:eeeee/=:fffff/1:tt/2:rr/=:hh"
Note for Swift, R, PowerShell
The prefix =: is replaced by E:
s1 = "mmmmm m nnnnn y&friend&Paul has heavy hats! &" s2 = "my frie n d Joh n has ma n y ma n y frie n ds n&" mix(s1, s2) --> "1:mmmmmm/E:nnnnnn/1:aaaa/1:hhh/2:yyy/2:dd/2:ff/2:ii/2:rr/E:ee/E:ss"
راه حل:
import java.util.*;
import java.util.stream.Collectors;
public class Mixing {
public static String mix(String s1, String s2) {
List<String> finalStr = new ArrayList();
for (char c = 'a'; c <= 'z'; c++) {
String s1_char = s1.replaceAll("[^"+c+"]+","");
String s2_char = s2.replaceAll("[^"+c+"]+","");
int s1_length = s1_char.length();
int s2_length = s2_char.length();
if(s1_length>1 || s2_length>1){
if(s1_length == s2_length){
finalStr.add("=:"+s1_char);
}
if(s1_length>s2_length){
finalStr.add("1:"+s1_char);
}
if(s1_length<s2_length){
finalStr.add("2:"+s2_char);
}
}
}
Comparator<String> length = (x,y) -> y.length()-x.length();
Comparator<String> type_value = (x,y) -> Character.compare(x.charAt(0),y.charAt(0));
return finalStr.stream().sorted(length.thenComparing(type_value)).collect(Collectors.joining("/"));
}
}import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
public class Mixing {
public static String mix(String s1, String s2) {
HashMap<Character,Count> map=new HashMap<>();
for(char c:s1.toCharArray()){
if(map.containsKey(c)){
map.get(c).times1++;
}
else{
Count count=new Count();
count.c=c;
count.times1++;
map.put(c,count);
}
}
for(char c:s2.toCharArray()){
if(map.containsKey(c)){
map.get(c).times2++;
}
else{
Count count=new Count();
count.c=c;
count.times2++;
map.put(c,count);
}
}
List<Count> list=new ArrayList<Count>(map.values());
Collections.sort(list);
StringBuilder sb=new StringBuilder();
for(Count c:list){
if(c.getMax()>1&&c.c>='a'&&c.c<='z'){
if(sb.length()!=0)
sb.append("/");
sb.append(c.getMaxIndexString());
sb.append(":");
for(int i=0;i<c.getMax();i++){
sb.append(c.c);
}
}
}
return sb.toString();
}
private static class Count implements Comparable<Count>{
char c;
int times1=0;
int times2=0;
@Override
public int compareTo(Count b){
if(b.getMax()!=getMax())
return b.getMax()-getMax();
if(getMaxIndexString()!=b.getMaxIndexString()){
return getMaxIndexString()-b.getMaxIndexString();
}
return c-b.c;
}
public int getMax(){
return Math.max(times1,times2);
}
public int getMaxIndex(){
return times1>times2?1:2;
}
public char getMaxIndexString(){
return times1==times2?'=':times1>times2?'1':'2';
}
}
}import java.util.Set;
import java.util.TreeSet;
public class Mixing {
public static String mix(final String s1, final String s2) {
int l1 = s1.length();
int l2 = s2.length();
final int[] a1 = new int[26];
final int[] a2 = new int[26];
char c1, c2;
for (int i = 0; i < l1; i++) {
c1 = s1.charAt(i);
if (c1 >= 'a' && c1 <= 'z') a1[c1 - 'a']++;
}
for (int i = 0; i < l2; i++) {
c2 = s2.charAt(i);
if (c2 >= 'a' && c2 <= 'z') a2[c2 - 'a']++;
}
final Set<String> result = new TreeSet<>((o1, o2) -> {
final int l = o1.length() - o2.length();
return l == 0 ? o1.compareTo(o2) : -l;
});
int l;
char w;
for (int i = 0; i < 26; i++) {
l1 = a1[i];
l2 = a2[i];
if (l1 <= 1 && (l1 ^ l2) <= 1) continue;
if (l1 > l2) {w = '1'; l = l1;}
else if (l1 < l2) {w = '2'; l = l2;}
else {w = '='; l = l1;}
final StringBuilder sb = new StringBuilder();
sb.append(w).append(':');
for (int j = 0; j < l; j++) {
sb.append((char) (i + 'a'));
}
result.add(sb.append('/').toString());
}
final StringBuilder res = new StringBuilder();
for (String s : result) res.append(s);
if (res.length() > 0) res.deleteCharAt(res.length() - 1);
return res.toString();
}
}import java.util.*;
import java.util.function.Function;
import java.util.stream.*;
public class Mixing {
public static String mix(String s1, String s2) {
s1 = s1.replaceAll("[^a-z]", "");
s2 = s2.replaceAll("[^a-z]", "");
Map<String,Long> map1 = Arrays.stream(s1.split("")).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
Map<String,Long> map2 = Arrays.stream(s2.split("")).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
Set<String> keySet = new HashSet<>(map1.keySet());
keySet.addAll(new HashSet<>(map2.keySet()));
List<String[]> result = new ArrayList<>();
for (String key:keySet) {
long value1 = map1.getOrDefault(key, 0L), value2 = map2.getOrDefault(key, 0L);
if ((value1 > 1) || (value2 > 1)) {
long compare = value1 - value2;
if (compare > 0)
result.add(new String[]{"1", Stream.generate(() -> key).limit(value1).collect(Collectors.joining())});
else if (compare < 0)
result.add(new String[]{"2", Stream.generate(() -> key).limit(value2).collect(Collectors.joining())});
else
result.add(new String[]{"=", Stream.generate(() -> key).limit(value1).collect(Collectors.joining())});
}
}
return result.stream()
.sorted(Comparator.comparing((String[] a) -> a[1].length()).reversed().thenComparing(a -> a[0]).thenComparing(a -> a[1]))
.map(a -> Arrays.stream(a).collect(Collectors.joining(":")))
.collect(Collectors.joining("/")).replaceFirst("/$", "");
}
}import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Mixing {
public static String mix(String s1, String s2) {
//统计字符串m1的各个字母频率
Map<String, Long> m1 = Stream.of(s1.replaceAll("[^a-z]","").split("")).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
//统计字符串m2的各个字母频率
Map<String, Long> m2 = Stream.of(s2.replaceAll("[^a-z]","").split("")).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
Set<String> set1 = m1.keySet();
Set<String> set2 = m2.keySet();
Set<String> set3 = new HashSet<>();
set3.addAll(set1);
set3.addAll(set2);
List<String> result = set3.stream().map(e -> {
StringBuilder sb = new StringBuilder();
if (m1.get(e) != null && m2.get(e) != null && m1.get(e) > 1 && m1.get(e) > m2.get(e)) {
for (int i = 0; i < m1.get(e); i++) {
sb.append(e);
}
return "1:"+sb.toString();
} else if (m1.get(e) != null && m2.get(e) != null && m1.get(e) > 1 && m1.get(e) == m2.get(e)) {
for (int i = 0; i < m1.get(e); i++) {
sb.append(e);
}
return "=:"+sb.toString();
} else if (m1.get(e) != null && m2.get(e) != null && m2.get(e) > 1 && m2.get(e) > m1.get(e)) {
for (int i = 0; i < m2.get(e); i++) {
sb.append(e);
}
return "2:"+sb.toString();
} else if (m1.get(e) != null && m2.get(e) == null && m1.get(e) > 1) {
for (int i = 0; i < m1.get(e); i++) {
sb.append(e);
}
return "1:"+sb.toString();
} else if (m2.get(e) != null && m1.get(e) == null && m2.get(e) > 1) {
for (int i = 0; i < m2.get(e); i++) {
sb.append(e);
}
return "2:"+sb.toString();
} else {
return "";
}
}).filter(e -> e.length()>0).sorted(Comparator.comparing(String::length).reversed().thenComparing(Function.identity())).collect(Collectors.toList());
return String.join("/", result);
}
public static void main(String[] args) {
System.out.println(Mixing.mix(" In many languages", " there's a pair of functions"));
}
}import java.util.*;
import java.util.stream.*;
public class Mixing {
public static String mix(String s1, String s2) {
StringBuffer sb = new StringBuffer("");
Map<Character, Long> counted1 = s1.replaceAll("[^a-z]", "").chars().boxed()
.collect(Collectors.groupingBy(s -> (char)((int)s), Collectors.counting()));
Map<Character, Long> counted2 = s2.replaceAll("[^a-z]", "").chars().boxed()
.collect(Collectors.groupingBy(s -> (char)((int)s), Collectors.counting()));
Map<Character, Long> counted3 = new TreeMap<Character, Long>(counted1);
counted2.forEach((k, v) -> {if (!counted1.containsKey(k) || counted1.get(k)<counted2.get(k)) counted3.put(k, v);});
Long max = Collections.max(counted3.values());
while(max>1) {
String appStr1 = "", appStr2 = "", appStr3 = "";
for(Map.Entry<Character, Long> entry: counted3.entrySet()) {
Character key = entry.getKey();
Long value = entry.getValue();
if(value == max) {
if(counted2.containsKey(key) ? counted2.get(key) < max : true)
appStr1 += "1:"+Stream.generate(() -> ""+key).limit(max).collect(Collectors.joining(""))+"/";
if(counted1.containsKey(key) ? counted1.get(key) < max : true)
appStr2 += "2:"+Stream.generate(() -> ""+key).limit(max).collect(Collectors.joining(""))+"/";
if(counted1.containsKey(key) && counted2.containsKey(key) ? counted1.get(key) == max && counted2.get(key) == max : false)
appStr3 += "=:"+Stream.generate(() -> ""+key).limit(max).collect(Collectors.joining(""))+"/";
counted3.put(key, (long)1);
}
}
sb.append(appStr1+appStr2+appStr3);
max = Collections.max(counted3.values());
}
return sb.length()==0 ? "" : sb.toString().substring(0,sb.length()-1);
}
}
