C#中字符串的最短子串

3回答

达令说

我相信这个问题有一个 O(n) 的解决方案如下：我们首先遍历字符串，找出其中有多少个不同的字符。在此之后，我们将表示子字符串左右索引的两个指针初始化为 0。我们还保留一个数组，用于计算子字符串中当前存在的每个字符的数量。如果没有包含所有字符，我们增加右指针以获得另一个字符。如果包含所有字符，我们增加左指针以便可能得到更小的子串。由于左指针或右指针在每一步都会增加，因此该算法应该在 O(n) 时间内运行。不幸的是，我不懂 C#。但是，我已经编写了一个 Java 解决方案（希望它具有类似的语法）。我没有对此进行严格的压力测试，所以我可能错过了一个边缘案例。import java.io.*;public class allChars { public static void main (String[] args) throws IOException { BufferedReader br = new BufferedReader (new InputStreamReader(System.in)); String s = br.readLine(); System.out.println(shortestSubstring(s)); } public static int shortestSubstring(String s) { //If length of string is 0, answer is 0 if (s.length() == 0) { return 0; } int[] charCounts = new int[26]; //Find number of distinct characters in string int count = 0; for (int i = 0; i < s.length(); i ++) { char c = s.charAt(i); //If new character (current count of it is 0) if (charCounts[c - 97] == 0) { //Increase count of distinct characters count ++; //Increase count of this character to 1 //Can put inside if statement because don't care if count is greater than 1 here //Only care if character is present charCounts[c - 97]++; } } int shortestLen = Integer.MAX_VALUE; charCounts = new int[26]; //Initialize left and right pointers to 0 int left = 0; int right = 0; //Substring already contains first character of string int curCount = 1; charCounts[s.charAt(0)-97] ++; while (Math.max(left,right) < s.length()) { //If all distinct characters present if (curCount == count) { //Update shortest length shortestLen = Math.min(right - left + 1, shortestLen); //Decrease character count of left character charCounts[s.charAt(left) - 97] --; //If new count of left character is 0 if (charCounts[s.charAt(left) - 97] == 0) { //Decrease count of distinct characters curCount --; } //Increment left pointer to create smaller substring left ++; } //If not all characters present else { //Increment right pointer to get another character right ++; //If character is new (old count was 0) if (right < s.length() && charCounts[s.charAt(right) - 97]++ == 0) { //Increment distinct character count curCount ++; } } } return shortestLen; }}

0 0

忽然笑

我希望我理解正确，这是获取最小字符串的代码。        string str = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec dictum elementum condimentum. Aliquam commodo ipsum enim. Vivamus tincidunt feugiat urna.";        char[] operators = { ' ', ',', '.', ':', '!', '?', ';' };        string[] vs = str.Split(operators);        string shortestWord = vs[0];        for (int i = 0; i < vs.Length; i++)        {            if (vs[i].Length < shortestWord.Length && vs[i] != "" && vs[i] != " ")            {                shortestWord = vs[i];            }        }        Console.WriteLine(shortestWord);

0 0

胡子哥哥

这似乎是一个O(n^2)问题。这并不理想；然而，我们可以做几件事来避免测试不能成为有效候选者的子字符串。我建议返回子字符串本身，而不是它的长度。这有助于验证结果。public static string ShortestSubstring(string input)我们首先计算 ['a' .. 'z'] 范围内每个字符的出现次数。我们可以'a'从一个字符中减去得到它从零开始的索引。var charCount = new int[26];foreach (char c in input) {    charCount[c - 'a']++;}最短的可能子字符串等于输入中不同字符的数量。int totalDistinctCharCount = charCount.Where(c => c > 0).Count();要计算子字符串中不同字符的数量，我们需要以下布尔数组：var hasCharOccurred = new bool[26];现在，让我们测试从不同位置开始的子字符串。totalDistinctCharCount最大起始位置必须允许子字符串至少与（最短的可能子字符串）一样长。string shortest = input;for (int start = 0; start <= input.Length - totalDistinctCharCount; start++) {    ...}return shortest;在这个循环中，我们有另一个循环来计算子字符串的不同字符。请注意，我们直接处理输入字符串以避免创建大量新字符串。我们只需要测试比之前找到的任何最短字符串都短的子字符串。因此内循环用作Math.Min(input.Length, start + shortest.Length - 1)限制。循环内容（代替...上面代码片段中的）：    int distinctCharCount = 0;    // No need to go past the length the previously found shortest.    for (int i = start; i < Math.Min(input.Length, start + shortest.Length - 1); i++) {        int chIndex = input[i] - 'a';        if (!hasCharOccurred[chIndex]) {            hasCharOccurred[chIndex] = true;            distinctCharCount++;            if (distinctCharCount == totalDistinctCharCount) {                shortest = input.Substring(start, i - start + 1);                break; // Found a shorter one, exit this inner loop.            }        }    }    // We cannot omit characters occurring only once    if (charCount[input[start] - 'a'] == 1) {        break; // Start cannot go beyond this point.    }    // Clear hasCharOccurred, to avoid creating a new array evey time.    for (int i = 0; i < 26; i++) {        hasCharOccurred[i] = false;    }进一步的优化是，当我们在输入字符串 ( charCount[input[start] - 'a'] == 1) 的起始位置遇到只出现一次的字符时，我们会立即停止。由于输入的每个不同字符都必须出现在子字符串中，因此该字符必须是子字符串的一部分。我们可以在控制台打印结果string shortest = ShortestSubstring(TestString);Console.WriteLine($"Shortest, Length = {shortest.Length}, \"{shortest}\"");

0 0