-
Notifications
You must be signed in to change notification settings - Fork 5
algorithm edit step ladder
Jongbin Oh edited this page Jun 8, 2013
·
1 revision
- 단어에 한 문자를 추가, 삭제, 변경한 다른 단어가 사전에 있는 경우 단방향 에지 생성
- 단방향 에지를 따라 최대 이동 가능한 단어의 개수는?
- 맵을 이용해 단어 Pool 생성.
- 한 문자를 추가, 삭제, 변경 하는 EditStep 을 실행했을 때 단어가 Pool 에 있으면 에지 생성
- EditStep 이 가능한 단어들끼리 에지 관계 테이블 생성(메모리 절약을 위해 맵사용)
- 단어 관계 테이블에 DFS!
- 내일 이 코드도 예쁘게 만들어 보도록 하겠습니다~
using System;
using System.Collections.Generic;
using System.Text;
using NUnit.Framework;
namespace ACM_EditStepLadders
{
class Program
{
public static string[] input =
{
"cat",
"dig",
"dog",
"fig",
"fin",
"fine",
"fog",
"log",
"wine"
};
static Dictionary<string, List<string>> rDic = new Dictionary<string, List<string>>();
static int 답 = 0;
static void Dfs(string src, int depth)
{
if (!rDic.ContainsKey(src))
{
if (답 < depth)
답 = depth;
return;
}
foreach (string s in rDic[src])
{
Dfs(s, depth + 1);
}
}
static void Main(string[] args)
{
// 1. > word pool 만들기
Dictionary<string, int> wDic = new Dictionary<string, int>();
List<string> wList = new List<string>();
Dictionary<int, List<string>> lenDic = new Dictionary<int, List<string>>();
for (int i = 0; i < input.GetLength(0); i++)
{
wList.Add(input[i]);
wDic[input[i]] = i;
if (!lenDic.ContainsKey(input[i].Length))
{
lenDic[input[i].Length] = new List<string>();
}
lenDic[input[i].Length].Add(input[i]);
}
// 2.1 > 단어간 관계 만들기
foreach (string src in wList)
{
// 고침
for (int i = 0; i < src.Length; i++)
{
char[] tmp = src.ToCharArray();
char init = tmp[i];
init++;
for (char c = init; c <= 'z'; c++)
{
tmp[i] = c;
string key = new string(tmp);
if (string.Compare(key, src, StringComparison.Ordinal) > 1)
{
if (wDic.ContainsKey(key))
{
if (!rDic.ContainsKey(src))
{
rDic[src] = new List<string>();
}
rDic[src].Add(key);
}
}
}
}
}
foreach (string src in wList)
{
// 추가
for (int i = 0; i <= src.Length; i++)
{
char[] tmp = src.ToCharArray();
// 끝에 한개 어떻게 하느냐가 문제.
// dog -> do 가 되는 케이스 때문에 헷갈.
char init = 'a';
if (i < src.Length)
{
init = tmp[i];
init++;
}
for (char c = init; c <= 'z'; c++)
{
string key = src.Insert(i, new string(c,1));
if (string.Compare(key, src, StringComparison.Ordinal) > 1)
{
if (wDic.ContainsKey(key))
{
if (!rDic.ContainsKey(src))
{
rDic[src] = new List<string>();
}
rDic[src].Add(key);
}
}
}
}
}
foreach (string src in wList)
{
// 삭제
for (int i = 0; i < src.Length; i++)
{
string key = src.Remove(i,1);
if (string.Compare(key, src, StringComparison.Ordinal) > 1)
{
if (wDic.ContainsKey(key))
{
if (!rDic.ContainsKey(src))
{
rDic[src] = new List<string>();
}
rDic[src].Add(key);
}
}
}
}
// 2.2 > 단어 관계 확인
foreach (KeyValuePair<string, List<string>> p in rDic)
{
Console.Write("{0} - ", p.Key);
foreach (string s in p.Value)
{
Console.Write("{0} ", s);
}
Console.WriteLine();
}
// 3. > DFS
foreach( string s in rDic.Keys )
{
Dfs(s, 1);
break;
}
// 4. > 문제 풀기
Console.WriteLine("\n최대 편집 사다리 단어 개수는 {0} 입니다.\n", 답);
}
}
[TestFixture]
public class Unitest
{
[TestFixtureSetUp]
public void SetUp()
{
}
[TestFixtureTearDown]
public void TearDown()
{
}
}
}
-
예제의 출력값이 5가 맞나요?
- wine -> fine -> fin -> fig -> dig -> dog -> fog -> log
- 여덟개가 넘는 경우도 나오는데 문제를 잘못 이해한가요? ^^;
- edit step ladder 는 lexicographically ordered sequence 라고 되어 있네요.
- 아 그렇네요~! ^^
-
그리고 이제서야 문제를 이해하자면 어떡하자는 건가욤? 지금 제가 안 간다고 군기 빠진 건가욤? 버럭
- 후후 벼락치기 하는거 아시면서.. ^^;
-
dog -> do 이게 사전 시퀀스 순서에 안맞는거 같아요;;
아이디어.
- 이미 찾아본 단어에 대해서는 더 이상 찾을 필요가 없다.
- 사전순으로 찾아보면 된다.
- 가장 높은 값을 유지한다. (DP, 다익스트라)
-
그러나 우려했던대로 Time limit exceeded 가 나는군요. 알고리즘을 확 고쳐야 할지, 문자열 쪽 부분을 최적화 해야 하는지 잘 모르겠습니다. 쩝...
-
map 이나 set, vector 대신 array 로 바꿔도 안 되네요. 힝... string 도 바꿔야 할까나...
/* @JUDGE_ID:parkpd 110401 Cpp "test" */ /* @BEGIN_OF_SOURCE_CODE */ #include <iostream> #include <vector> #include <set> #include <string> #include <strstream> #include <algorithm> #include <map> #include <math.h> //#define _UNIT_TEST using namespace std; namespace ATUtil { bool IsInRange(int value, int from, int to) { return (from <= value) && (value <= to); } int ConvertToIndex(char c) { if ('a' <= c && c <= 'z') { return c - 'a'; } else { return -1; } } char ConvertToChar(int i) { return (char)i + 'a'; } typedef map<int, int> IntDB; typedef vector<int> Ints; }; using namespace ATUtil; #ifdef _UNIT_TEST #include "../UnitTest++/src/UnitTest++.h" int main() { UnitTest::RunAllTests(); char temp; cin >> temp; return 0; } #endif // code implement namespace ATCode { string g_Words[25000]; int g_Ladder[25000]; ////////////////////////////////////////////////////////////////////////// // CEditStepLadder class CEditStepLadder { public: CEditStepLadder() : m_Longest(0), m_WordSize(0) {} int m_Longest; int m_WordSize; void Insert(const string& str); void Find(size_t from, const string& word); int GetLongestEditStepLadder(); }; void CEditStepLadder::Insert(const string& str) { g_Words[m_WordSize] = str; g_Ladder[m_WordSize] = 1; m_WordSize++; } void CEditStepLadder::Find(size_t from, const string& word) { int left = (int)from + 1; // 나보다 사전순으로 높은 단어부터 검색 시작 int right = m_WordSize - 1; int mid; while (left <= right) { mid = (left + right) / 2; int cmp = strcmp(g_Words[mid].c_str(), word.c_str()); if (0 == cmp) { // ladder step 이 더 긴 경우에만 업데이트한다. int& currentWordStep = g_Ladder[from]; int& foundWordStep = g_Ladder[mid]; if ((foundWordStep < currentWordStep + 1)) { foundWordStep = currentWordStep + 1; if (m_Longest < foundWordStep) { m_Longest = foundWordStep; } } break; } else if (0 < cmp) { right = mid - 1; } else { left = mid + 1; } } } int CEditStepLadder::GetLongestEditStepLadder() { vector<char> letter; letter.reserve(26); for (char c = 'a'; c <= 'z'; ++c) { letter.push_back(c); } const int letterSize = (int)letter.size(); string originalWord; string word; for (int it = 0; it < m_WordSize; ++it) { originalWord = g_Words[it]; word = originalWord; size_t wordSize = word.size(); // 한 글자가 바뀐 경우 for (size_t i = 0; i < wordSize; ++i) { word = originalWord; // reset for (int j = 0; j < letterSize; ++j) { word[i] = letter[j]; Find(it, word); } } // 한 글자를 더한 경우. // 3 자짜리 글자라면, 글자가 추가될 수 있는 곳은 4 군데다. for (size_t i = 0; i <= wordSize; ++i) { word = originalWord; // reset word.insert(word.begin() + i, ' '); for (int j = 0; j < letterSize; ++j) { word[i] = letter[j]; Find(it, word); } } // 한 글자를 뺀 경우 for (size_t i = 0; i < wordSize; ++i) { word = originalWord; // reset word.erase(i, 1); Find(it, word); } } return m_Longest; } /////////////////////////////////////////////////////////////// // CConsole class CConsole { public: static void ConsoleTest(istream& input, ostream& output); }; void CConsole::ConsoleTest(istream& input, ostream& output) { CEditStepLadder ladder; string word; while (input >> word) { ladder.Insert(word); } int ret = ladder.GetLongestEditStepLadder(); output << ret; }; } using namespace ATCode; #ifndef _UNIT_TEST int main() { CConsole::ConsoleTest(cin, cout); return 0; } #else // tests struct FixtureConsole { stringstream input; stringstream output; }; TEST_FIXTURE(FixtureConsole, ConsoleTest) { string s = "test"; string s1 = "test1"; CHECK(s < s1); string s2 = "aest"; string s3 = "test"; CHECK(s2 < s3); } TEST_FIXTURE(FixtureConsole, ConsoleTest1) { input << "cat\n" "dig\n" "dog\n" "fig\n" "fin\n" "fine\n" "fog\n" "log\n" "wine\n" ; CConsole::ConsoleTest(input, output); CHECK_EQUAL("5", output.str()); } #endif /* @END_OF_SOURCE_CODE */
- 많이 늦었습니다. ㅋ
Public Class StepLadder
Function GetEditStepLadders(ByVal inputs As List(Of String)) As Integer
Dim words As List(Of Word) = CreateWordList(inputs)
CalcWordSteps(words)
Return GetMaxSteps(words)
End Function
Sub CalcWordSteps(ByVal words As List(Of Word))
Dim maxSubStep As Integer
For i As Integer = 1 To words.Count - 1
Dim aWord As Word = words(i)
For j As Integer = 0 To i - 1
Dim compared As Word = words(j)
If IsEditStep(aWord, compared) Then
If compared.Steps > maxSubStep Then maxSubStep = compared.Steps
End If
Next j
aWord.SetSteps(aWord.Steps + maxSubStep)
Next i
End Sub
Function IsEditStep(ByVal first As Word, ByVal second As Word) As Boolean
Dim str1 As String
Dim str2 As String
If first.Str < second.Str Then
str1 = first.Str
str2 = second.Str
Else
str1 = second.Str
str2 = first.Str
End If
Dim isOneModified As Boolean = IsModifiedOne(str1, str2)
Dim isOneRemoved As Boolean = IsRemovedOne(str1, str2)
Dim isOneAdded As Boolean = IsAddeddOne(str1, str2)
Return (isOneModified Or isOneRemoved Or isOneAdded)
End Function
Function IsRemovedOne(ByVal first As String, ByVal second As String) As Boolean
Dim ch1() As Char = first.ToCharArray()
Dim ch2() As Char = second.ToCharArray()
If ch1.Length <> ch2.Length + 1 Then Return False
For Each c2 As Char In ch2
If Not IsContain(c2, ch1) Then Return False
Next
Return True
End Function
Function IsContain(ByVal aChar As Char, ByVal chs() As Char) As Boolean
For Each ch As Char In chs
If aChar = ch Then Return True
Next
Return False
End Function
Function IsModifiedOne(ByVal first As String, ByVal second As String) As Boolean
Dim ch1() As Char = first.ToCharArray()
Dim ch2() As Char = second.ToCharArray()
If ch1.Length <> ch2.Length Then Return False
Dim diffCount As Integer
For i As Integer = 0 To ch1.Length - 1
If ch1(i) <> ch2(i) Then diffCount += 1
If diffCount >= 2 Then Return False
Next
Return (diffCount = 1)
End Function
Function IsAddeddOne(ByVal first As String, ByVal second As String) As Boolean
Return IsRemovedOne(second, first)
End Function
Function CreateWordList(ByVal inputs As List(Of String)) As List(Of Word)
inputs.Sort()
Dim words As List(Of Word) = New List(Of Word)
For Each str As String In inputs
words.Add(New Word(str))
Next
Return words
End Function
Function GetMaxSteps(ByVal words As List(Of Word)) As Integer
Dim maxSteps As Integer
For Each aWord As Word In words
If aWord.Steps > maxSteps Then maxSteps = aWord.Steps
Next
Return maxSteps
End Function
End Class
Public Class Word
Private _str As String
ReadOnly Property Str()
Get
Return _str
End Get
End Property
Private _steps As Integer = 1
ReadOnly Property Steps()
Get
Return _steps
End Get
End Property
Sub SetSteps(ByVal steps As Integer)
_steps = steps
End Sub
Sub New(ByVal str As String)
_str = str
End Sub
End Class
<TestClass()> _
Public Class StepLadderTest
Private _inputs As List(Of String)
Private _ladder As StepLadder = New StepLadder
Private _words As List(Of Word)
<TestInitialize()> _
Public Sub MyTestInitialize()
Dim strs() As String = {"cat", "dig", "dog", "fig", "fin", "fine", "fog", "log", "wine"}
_inputs = New List(Of String)(strs)
_words = _ladder.CreateWordList(_inputs)
End Sub
<TestMethod()> _
Public Sub SortTest()
_inputs.Sort()
Assert.AreEqual("cat", _inputs(0))
End Sub
<TestMethod()> _
Public Sub CreateWordListTest()
Assert.AreEqual(9, _words.Count)
Assert.AreEqual("cat", _words(0).Str)
End Sub
<TestMethod()> _
Public Sub IsContainTest()
Dim chs() As Char = {"a"c, "b"c}
Assert.IsTrue(_ladder.IsContain("a"c, chs))
Assert.IsFalse(_ladder.IsContain("c"c, chs))
End Sub
<TestMethod()> _
Public Sub IsRemovedOneTest()
Assert.IsTrue(_ladder.IsRemovedOne("fine", "fne"))
Assert.IsFalse(_ladder.IsRemovedOne("fin", "fine"))
Assert.IsFalse(_ladder.IsRemovedOne("fine", "fe"))
End Sub
<TestMethod()> _
Public Sub IsAddedOneTest()
Assert.IsTrue(_ladder.IsAddeddOne("fin", "fine"))
Assert.IsFalse(_ladder.IsAddeddOne("fine", "fie"))
Assert.IsFalse(_ladder.IsAddeddOne("fi", "fine"))
End Sub
<TestMethod()> _
Public Sub IsModifiedOneTest()
Assert.IsTrue(_ladder.IsModifiedOne("fig", "dig"))
Assert.IsTrue(_ladder.IsModifiedOne("fog", "dog"))
Assert.IsFalse(_ladder.IsModifiedOne("fog", "fo"))
Assert.IsFalse(_ladder.IsModifiedOne("fog", "foge"))
Assert.IsFalse(_ladder.IsModifiedOne("fog", "dig"))
End Sub
<TestMethod()> _
Public Sub IsEditStepTest()
Dim word1 As Word = New Word("fine")
Dim word2 As Word = New Word("fin")
Assert.IsTrue(_ladder.IsEditStep(word1, word2))
Assert.IsTrue(_ladder.IsEditStep(word2, word1))
Assert.IsFalse(_ladder.IsEditStep(word1, word1))
End Sub
<TestMethod()> _
Public Sub CalcWordStepsTest()
_ladder.CalcWordSteps(_words)
Assert.AreEqual("dog", _words(2).Str)
Assert.AreEqual(2, _words(2).Steps)
Assert.AreEqual("log", _words(7).Str)
Assert.AreEqual(5, _words(7).Steps)
End Sub
<TestMethod()> _
Public Sub GetEditStepLaddersTest()
Assert.AreEqual(5, _ladder.GetEditStepLadders(_inputs))
End Sub
End Class