1

我今天必须为面试做一个测试，问题是获得字典上最小和最大的子字符串（换句话说，按名称排序）。

链接- 完成函数 SmallestAndLargestSubstring，它以一个由小写英文字母 (az) 组成的字符串 S 作为其参数，并返回以元音开头和辅音结尾的按字典顺序排列的最小和最大子字符串。

我的算法通过了基本的测试用例，但其他大多数都失败了。它不是最有效的代码，但它是最快的编写代码。

static String[] SmallestAndLargestSubstring(String s) {

    ArrayList<Character> vowelList = new ArrayList<Character>();
    vowelList.add('a');
    vowelList.add('e');
    vowelList.add('i');
    vowelList.add('o');
    vowelList.add('u');

    ArrayList<Character> consonantList = new ArrayList<Character>();
    for (char c='a'; c<='z'; c++) {
        if (!vowelList.contains(c))
            consonantList.add(c);
    }

    ArrayList<String> substringList = new ArrayList<String>();

    for (int i=0; i<s.length(); i++) {
        char c = s.charAt(i);
        if (vowelList.contains(c)) {
            String substring = "";
            substring+=c;
            for (int j=i+1; j<s.length(); j++) {
                char c2 = s.charAt(j);
                substring+=c2;
                if (consonantList.contains(c2)) {
                    substringList.add(substring);
                }
            }
        }
    }

    Collections.sort(substringList);

    String[] outputAdapter = new String[2];
    outputAdapter[0]=substringList.get(0);
    outputAdapter[1]=substringList.get(substringList.size()-1);

    return outputAdapter;
}

无论如何，我想弄清楚我哪里出错了，所以我对测试用例进行了逆向工程，以找出传入的输入是什么，希望我能够找出我的算法出了什么问题。

这是我发现的，这些是我的答案（根据测试用例是错误的）。

输入

字符串 s = "azizezozuzawwwwwwwwwuzzzzzzzzabbbbbbbaaaabbbboiz"

我的答案

最小的=“aaaab”；

最大 = "uzzzzzzzzabbbbbbbaaaabbbboiz";

但是对于我的生活，我无法弄清楚我的错误在哪里。这是我的子字符串的完整列表，从最小到最大排序。链接到排序结果

在过去的 3 个小时里，我一直在绞尽脑汁。如果有人能弄清楚我的错误在哪里，我将不胜感激。

编辑：这里还有 3 个测试用例。我的答案与这些测试用例答案相匹配。

字符串 = "aba"; 最小=“ab”；最大=“ab”；

字符串 = "aab"; 最小=“aab”；最大=“ab”；

string = "abababababbaaaaaaaaaaaaaaaz"; 最小的=“aaaaaaaaaaaaaaaz”；最大 = "az";

4

1 回答 1

0 
/*
It is the Basic code to Obtain Substring which start with Vowel and End up with Consonant. It is going to print on the Basis of Name Comparable, The first and the Last Substring in the List.Similarly we can achieve on the basis of length, the firt and last Substring using different comparator function.
*/

public class StringSubsequencesStartVowelEndConsonant {
    static List<String> subsequence = new LinkedList<>();

    public static void main(String[] args) {        
        Scanner in = new Scanner(System.in);
        System.out.println("Enter the String:\n");
        String string = in.next();
        findSubstring(string);      
    }

    private static void findSubstring(String string) {      
        for(int i=0;i<string.length();i++){
            if(isVowel(string.charAt(i))){              
                for(int j=string.length()-1;j>=i;j--){
                    if(isConsonant(string.charAt(j))){                      
                        String subString = string.substring(i,j+1);
                        subsequence.add(subString);
                    }
                }
            }
        }       
        Collections.sort(subsequence);
        for(String str : subsequence){
            System.out.print(str+" ");
        }
        System.out.println();
        System.out.println(subsequence.get(0));
        System.out.println(subsequence.get(subsequence.size()-1));      
    }
    private static boolean isConsonant(char chars) {
        return !(chars=='a'|| chars=='e'||chars=='i'||chars=='o'||chars=='u');
    }
    private static boolean isVowel(char chars) {
        return (chars=='a'|| chars=='e'||chars=='i'||chars=='o'||chars=='u');
    }
}
于 2017-10-01T08:17:59.930 回答