Перечислять все возможные названия с номером телефона


В программе нужно ввести номер, а затем рассчитать все возможные именем мы можем сформировать по следующему правилу:

2: A,B,C     5: J,K,L    8: T,U,V
3: D,E,F     6: M,N,O    9: W,X,Y
4: G,H,I     7: P,R,S

Так же, как и на клавиатуре телефона. Q и Z были исключены (для простоты, я считаю)

Например 4734 производит

GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI
GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI
GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI
HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI
HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI
IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI
ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI

Цифры в введенное число может варьироваться от 1 до 12.

Я пытался сделать это с помощью рекурсии.

import java.util.*;
import java.io.*;
public class namenum{
        public static void main(String[] args) throws Exception{

        Scanner sc = new Scanner(new File("namenum.in"));

        PrintWriter pw  = new PrintWriter(new File("namenum.out"));
        String n = sc.next();
        ArrayList<String> ans = new ArrayList<>();
        List<Character> arr2 = new ArrayList<>();
        arr2.add('A');
        arr2.add('B');
        arr2.add('C');

        List<Character> arr3 = new ArrayList<>();
                arr3.add('D');
        arr3.add('E');
        arr3.add('F');

        List<Character> arr4 = new ArrayList<>();
        arr4.add('G');
        arr4.add('H');
        arr4.add('I');

        List<Character> arr5 = new ArrayList<>();
        arr5.add('J');
        arr5.add('K');
        arr5.add('L');

        List<Character> arr6 = new ArrayList<>();
        arr6.add('M');
        arr6.add('N');
        arr6.add('O');
        List<Character> arr7 = new ArrayList<>();
        arr7.add('P');
        arr7.add('Q');
        arr7.add('R');


        List<Character> arr8 = new ArrayList<>();
        arr8.add('T');
        arr8.add('U');
        arr8.add('V');

        List<Character> arr9 = new ArrayList<>();
        arr9.add('W');
        arr9.add('X');
        arr9.add('Y');

        List<List<Character>> Lists = new ArrayList<>();
        Lists.add(arr2);
        Lists.add(arr3);
        Lists.add(arr4);
        Lists.add(arr5);
        Lists.add(arr6);
        Lists.add(arr7);
        Lists.add(arr8);
        Lists.add(arr9);

        List<String> result = new ArrayList<String>();
        genPermutations(Lists, result, 0, "");
        boolean ansFound = false;
        for(int i = 0; i< result.size(); i++){
            String name = result.get(i);
            if(isInDict(name)){
                pw.println(name);
                ansFound = true;
            }

        }
        if (!ansFound){
            pw.println("NONE");
        }
        pw.close();


    }
    static boolean isInDict(String name) throws Exception{
        boolean ans = false;
        Scanner dict = new Scanner(new File("dict.txt"));
        while(dict.hasNext()){
            if(dict.next() == name){
                ans = true;
                break;
            }
        }
        return ans;

    }

    static void genPermutations(List<List<Character>> Lists, List<String> result, int depth, String current){
        if(depth == Lists.size()){
            result.add(current);
            return ;
        }
        for(int i = 0; i<Lists.get(depth).size();i++){
            genPermutations(Lists, result, depth+1,current+Lists.get(depth).get(i));
        }
    }
    }

Но он использует больше времени (2.128 секунд, чтобы быть точным), чем принято в 1 секунду и меня превышено ограничение по времени приговоре.

Вопрос может быть найден здесь USACO

Каковы способы, которыми я могу упростить программу?



Комментарии
1 ответ

Без ссылки, я могу только сделать некоторые предположения, так что я собираюсь дать несколько глобальных замечаний:


  • При проверке, если что-то содержится в словаре, вы каждый раз читать файл снова. Во-вторых, можно линейно через нее, чтобы определить, если имя содержится в нем или нет. Это очень, очень медленно. Это потому что у вас есть некоторые ограничения памяти? Потому что иначе, это будет намного быстрее, чтобы прочитать его в начале, и использовать HashSet чтобы проверить наличие.

  • Вы должны быть в состоянии прочитать весь файл в память, возможно, вы могли бы даже создать сопоставление между именами и сочетаниями клавиш, которые составляют это имя, по предвычисление этого. Я думаю, что это было бы оптимальным решением?

  • genPermutations не работает. Передать глубину, которая по сути является ключевой индекс, и генерировать все перестановки из этого ключа до финального ключа. Если вы все-таки сохранить и исправить genPermutations способ, у вас есть еще одна точка, которая может быть улучшена. Как я уже отмечал ранее, если вы хотели посмотреть на получаемые результаты, можно заметить много дублирования. Возьмите свой 4734 например, которые, среди прочего, генерирует GPDG, HPDGи IPDG. Три строки равны, за исключением первой буквы. Это означает, что вы вычисляете много одинаковых вещей. Это может быть кэширован.

Некоторые незначительные замечания:


  • Имена классов должны быть прописными (или лучше, CamelCase), например, NameNum

  • Имена переменных должны начинаться со строчной, так List<List<Character>> lists = new ArrayList<>();

  • Не использовать равенство ссылок с StringС вместо того, чтобы использовать equals метод. Вы могли бы получить неожиданные результаты.

1
ответ дан 4 марта 2018 в 04:03 Источник Поделиться