문자열의 반복 문자 테스트

Question

문자열을 사용하여 작업하고 있으며 문자열 (대개 작은 하나의 < 10 문자)에 반복 문자가 포함되어 있는지 확인해야하는 시나리오가 있습니다.

`ABCDE` // does not contain repeats 
`AABCD` // does contain repeats, ie A is repeated 

나는 수있는 string.ToCharArray을 통해 루프()와 문자 []의 다른 모든 문자에 대한 각 문자를 테스트하지만 어쩌면 난 그냥 커피가 필요합니다 .... 분명 뭔가를 놓친 거지 같은 느낌. 누구든지 도와 줄 수 있습니까?

편집 : 순서는 중요하지 않습니다 때문에 문자열이 정렬됩니다

그래서 ABCDA => AABCD

반복의 빈도도 중요하다, 그래서이 반복 쌍의 경우 알 필요가

Answer 1

문자열이 짧으면 루핑과 테스트가 가장 간단하고 효율적인 방법 일 수 있습니다. 내 말은 당신이 일 수있다. 해시 세트를 만들고 (사용중인 플랫폼에 관계없이) 캐릭터를 반복하며, 캐릭터가 이미 세트에 포함되어 있고 그렇지 않은 경우 세트에 추가하면 실패한다. 그러나 이것은 모든 이점을 제공 할 가능성이있다. 문자열이 더 길 때.

편집 : 이제 알 수 있듯이 mquander's answer이 (가) 가장 좋은 IMO입니다. 여기에 구현입니다 :

public static bool IsSortedNoRepeats(string text) 
{ 
    if (text.Length == 0) 
    { 
     return true; 
    } 
    char current = text[0]; 
    for (int i=1; i < text.Length; i++) 
    { 
     char next = text[i]; 
     if (next <= current) 
     { 
      return false; 
     } 
     current = next; 
    } 
    return true; 
} 

더 짧은 대안 당신은 인덱서를 사용 반복 괜찮다면 :

가

public static bool IsSortedNoRepeats(string text) 
{ 
    for (int i=1; i < text.Length; i++) 
    { 
     if (text[i] <= text[i-1]) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

편집 : 좋아, "주파수"면, 내가 라운드 문제를 켤 것을 약간. 나는 여전히 문자열이 정렬되어 있다고 가정 할 것이므로 우리가 알고 자하는 것은 가장 긴 실행의 길이입니다. 반복이 없을 때 가장 긴 실행 길이는 0 (빈 문자열의 경우) 또는 1 (비어 있지 않은 문자열의 경우)이됩니다. 그렇지 않으면 2 이상이됩니다.

우선 캐릭터 별 버전 :

public static int LongestRun(string text) 
{ 
    if (text.Length == 0) 
    { 
     return 0; 
    } 
    char current = text[0]; 
    int currentRun = 1; 
    int bestRun = 0; 

    for (int i=1; i < text.Length; i++) 
    { 
     if (current != text[i]) 
     { 
      bestRun = Math.Max(currentRun, bestRun); 
      currentRun = 0; 
      current = text[i]; 
     } 
     currentRun++; 
    } 
    // It's possible that the final run is the best one 
    return Math.Max(currentRun, bestRun); 
} 

지금 우리는 또한 IEnumerable<T>에 일반적인 확장 방법으로이 작업을 수행 할 수 있습니다

public static int LongestRun(this IEnumerable<T> source) 
{ 
    bool first = true; 
    T current = default(T); 
    int currentRun = 0; 
    int bestRun = 0; 

    foreach (T element in source) 
    { 
     if (first || !EqualityComparer<T>.Default(element, current)) 
     { 
      first = false; 
      bestRun = Math.Max(currentRun, bestRun); 
      currentRun = 0; 
      current = element; 
     } 
    } 
    // It's possible that the final run is the best one 
    return Math.Max(currentRun, bestRun); 
} 

이 그럼 당신은 예를 들어 "AABCD".LongestRun()를 호출 할 수 있습니다.

Answer 2

업데이트 이제 카운트를 유지하려면 카운터 배열이 필요합니다.

1 비트가 고유 한 문자를 나타내는 비트 배열을 유지합니다. 문자를 만날 때 비트를 켜고 문자열을 한 번 실행합니다. 비트 배열 인덱스와 문자 집합을 매핑하면 결정할 수 있습니다. 특정 비트가 이미 켜져 있는지 확인하면 중단하십시오.

Answer 3

문자열이 정렬 된 경우 각 문자를 차례로 기억하고 다음 문자가 마지막 문자와 동일하지 않은지 확인하십시오.

그 외, 10 자 미만의 문자열의 경우 나머지 모든 것에 대해 각 문자를 테스트하는 것이 다른 대부분의 것보다 빠르거나 빠를 것입니다. 다른 주석 작성자가 제안한 비트 벡터는 더 빠를 수 있습니다 (작은 문자 집합이있는 경우 도움이됩니다.)

보너스 :

int longestRun = 
    s.Select((c, i) => s.Substring(i).TakeWhile(x => x == c).Count()).Max(); 

그래서, OK, 그것은 매우 빠르게 아니다 : 여기 존의 기능을 구현하는 매끄러운 LINQ 솔루션입니다! 그게 문제가 있니?!

:-)

Answer 4

나는 그것을 달성 할 수있는 가장 쉬운 방법이 간단한 정규식을 사용하는 것입니다 생각

bool foundMatch = false; 
foundMatch = Regex.IsMatch(yourString, @"(\w)\1"); 

당신이 경기에 대한 자세한 내용은 (시작, 길이 등)

 Match match = null; 
    string testString = "ABCDE AABCD"; 
    match = Regex.Match(testString, @"(\w)\1+?"); 
    if (match.Success) 
    { 
     string matchText = match.Value; // AA 
     int matchIndnex = match.Index; // 6 
     int matchLength = match.Length; // 2 
    } 

필요한 경우

Answer 5

/(.).*\1/ 

(또는 무엇이든지 정규식 라이브러리의 구문에 해당)

문자열의 모든 문자로 역 추적하고 앞으로 다시 스캔하므로 가장 효율적이지 않습니다. 정규 표현식을지지하지 않습니다. 당신은 간결함을 원한다면 ...

Answer 6

는 3.5을 사용하고 있기 때문에, 당신은 하나의 LINQ 쿼리에서이 작업을 수행 할 수 있습니다 :

한 번 입력에 이상이 나타납니다 각 문자에 대해

var results = stringInput 
    .ToCharArray() // not actually needed, I've left it here to show what's actually happening 
    .GroupBy(c=>c) 
    .Where(g=>g.Count()>1) 
    .Select(g=>new {Letter=g.First(),Count=g.Count()}) 
; 

,이 제공됩니다 당신에게 등장 인물과 사건의 수를 알려주세요.

Answer 7

이 매우 빠르게 문자열 중복을 포함 경우 당신을 말할 것이다 :

bool containsDups = "ABCDEA".Length != s.Distinct().Count(); 

은 그냥 원래 길이에 대한 고유 한 문자의 수를 확인합니다. 서로 다른 경우에, 당신은 ... 중복있어

편집 : 나는이 비록 당신의 편집에 당신이 언급 DUPS의 주파수 처리를하지 않는 것 같아요 ...하지만 이미 여기에 몇 가지 다른 제안 그것들을 처리하십시오, 그래서 나는 그들 중 다수가 이미 당신에게 합리적으로 우아한 솔루션을 제공함을 알기 때문에 코드를 게시하지 않을 것입니다. 특히 LINQ 확장을 사용하는 Joe의 구현이 마음에 듭니다.

Answer 8

같은 것에 대해 어떻게 :

string strString = "AA BRA KA DABRA"; 

var grp = from c in strString.ToCharArray() 
     group c by c into m 
     select new { Key = m.Key, Count = m.Count() }; 

foreach (var item in grp) 
{ 
    Console.WriteLine(
     string.Format("Character:{0} Appears {1} times", 
     item.Key.ToString(), item.Count)); 
} 

Answer 9

카운트를 유지하기 위해 사전을 사용할 수 있습니다 당신을 작동 할 순서가 없다 :

String input = "AABCD"; 
var result = new Dictionary<Char, int>(26); 
var chars = input.ToCharArray(); 
foreach (var c in chars) 
{ 
    if (!result.ContainsKey(c)) 
    { 
     result[c] = 0; // initialize the counter in the result 
    } 
    result[c]++; 
} 

foreach (var charCombo in result) 
{ 
    Console.WriteLine("{0}: {1}",charCombo.Key, charCombo.Value); 
} 

Answer 10

존이 설명 된 해시 솔루션은 아마도입니다 베스트. HybridDictionary는 작고 큰 데이터 세트에서 잘 작동하므로 사용할 수 있습니다. 문자가 키이고 값은 빈도입니다. (추가가 실패하거나 .Contains (키)에 대해 HybridDictionary가 true를 반환 할 때마다 주파수 업데이트)

Answer 11

나는 그물에 대한 정보를 찾기 시작했고 다음 해결책을 얻었습니다.

string input = "aaaaabbcbbbcccddefgg"; 
     char[] chars = input.ToCharArray(); 
     Dictionary<char, int> dictionary = new Dictionary<char,int>(); 

     foreach (char c in chars) 
     { 
      if (!dictionary.ContainsKey(c)) 
      { 
       dictionary[c] = 1; // 
      } 
      else 
      { 
       dictionary[c]++; 
      } 
     } 

     foreach (KeyValuePair<char, int> combo in dictionary) 
     { 
      if (combo.Value > 1) //If the vale of the key is greater than 1 it means the letter is repeated 
      { 
       Console.WriteLine("Letter " + combo.Key + " " + "is repeated " + combo.Value.ToString() + " times"); 
      } 

     } 

는 내가 면접관이이 문제를 해결하라고하는 면접을했다, 그것은 도움이되기를 바랍니다 그리고 그것이 일반적인 질문을 이해합니다.