Sorted String with input characters pattern-CodePudding

I have the methode sortString, that have to sort characters in the string with pattern that i add. For example:

if the pattern : List patter= Arrays.asList('a', 'b', 'c', 'd', 'z') and the inputString is "bbacrrt" sortString have to return "abbcrrt" symbols that doesn't included in pattern have to add in the end of return string, order of this symbols doesn't metter.

In ideal way difficulty should be O(n).

 private static String sortString(String inputString, List<Character> pattern) {
    List<Character> inputlist = convert(inputString); // method convert create List<Character> from String
    List<Character> returnedList = new ArrayList<>(Collections.nCopies(inputlist.size(), ' '));
    Map<Character, Integer> map = new HashMap<>();
    boolean isAdded = false;

    for (int i = 0; i < pattern.size(); i  ) {
        map.put(pattern.get(i), i);
    }

    for (int i = 0; i < inputlist.size(); i  ) {
        for (int j = 0; j < pattern.size(); j  ) {
            if (inputlist.get(i) == pattern.get(j)) {
                if (returnedList.get(map.get(pattern.get(j))) == pattern.get(j)) {
                    returnedList.add(map.get(pattern.get(j)), inputlist.get(i));
                } else {
                    if (map.get(pattern.get(j)) - 1 < 0) {
                        returnedList.add(map.get(pattern.get(j)), inputlist.get(i));
                    } else {
                        returnedList.add(map.get(pattern.get(j))   1, inputlist.get(i));
                    }
                }
                isAdded = true;
            }
        }
        if (!isAdded) {
            returnedList.add(inputlist.get(i));
        }
        isAdded = false;
    }
    return returnedList.toString();
}

Could you help me?

CodePudding user response：

My initial thought was to use a HashMap<String, ArrayList> to store the returnList. Use the String part of the HashMap to store each character of the pattern and ArrayList to store each character of the inputList as you walked through that string.

When you want the final output, loop through the HashMap using the pattern as the index.

CodePudding user response：

When sorting characters, it's usually a counting sort. Then use a boolean array to mark the characters in the pattern. When you build the string, use the boolean array to check if the character should be append in the sort section or the unsorted section. Use the count array to append the number of characters to the string.

This is an O(n) solution.

import java.util.*;

public class Main {

    public static void main(String[] args) {
        List<Character> pat = Arrays.asList('a', 'c',  'z');
        String s  = "atttbbacrrt";
        System.out.println(sort(pattern, input));
    }
    
    static String sort(List<Character> pat, String s) {
       boolean[] mustHave = new boolean[26];
       int[]     count    = new int[26];
       for(char c: pat) mustHave[c-'a'] = true;
       for(char c: s.toCharArray()) count[c-'a']  ;
       
       StringBuilder sorted    = new StringBuilder();
       StringBuilder unsorted  = new StringBuilder();
       for(int i = 0; i < 26; i  ) {
          StringBuilder sb = mustHave[i] ? sorted : unsorted;
          for(int j = 0; j < count[i]; j  ) sb.append((char)('a' i));
       }
       return sorted.toString()   unsorted.toString();
    }
}

Output:

aacbbrrtttt