[기초 알고리즘] String

1. Anagram

• 길이가 같고, 같은 문자로 구성된 두 문자열을 가리킴

 

예시

• stressed→desserts
• Elvis→lives 
• Permission to dance → Stories on Pandemic

 

코드

private static int CHARACTER_RANGE= 256;

public boolean isAnagramCounting(String string1, String string2) {
    if (string1.length() != string2.length()) {
        return false;
    }
    int count[] = new int[CHARACTER_RANGE];
    for (int i = 0; i < string1.length(); i++) {
        count[string1.charAt(i)]++;
        count[string2.charAt(i)]--;
    }
    for (int i = 0; i < CHARACTER_RANGE; i++) {
        if (count[i] != 0) {
            return false;
        }
    }
    return true;
}

 

2. Palindrom

• 문자열의 중심으로부터 모든 쌍이 대칭되는 문자열

 

예시

• abdba
• 1234567654321

 

구현

boolean validPalindrome(String s) {
   for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
       if (Character.toLowerCase(s.charAt(i)) == Character.toLowerCase(s.charAt(j))) continue;
       
       return false;
   }
   
   return true;
}

 

3. Compression

• 문자열에서 같은 문자가 연속으로 나타나면, 그 문자의 반복 횟수를 사용해 압축하기

 

알고리즘

Run-Length Encoding (RLE)

• 연속된 문자를 문자와 반복 횟수로 표현
• AABBBCCCC -> A2B3C4

 

Haffman Coding

• 문자 매핑
  • 자주 등장하는 문자에 작은 값의 코드
  • 덜 등장하는 문자에 큰 값의 코드
• 가변 길이를 효율적으로 압축

 

 

 

출처

• codegym - 문자열을 확인하는 Java 프로그램은 Palindrom입니다.
• Baeldung - check if two strings are anagrams in java
• Wiki - Anagram