algorithm edit step ladder - andstudy/forge GitHub Wiki

Outbreak

문제 요약

단어에 한 문자를 추가, 삭제, 변경한 다른 단어가 사전에 있는 경우 단방향 에지 생성
단방향 에지를 따라 최대 이동 가능한 단어의 개수는?

문제 해결

맵을 이용해 단어 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 이게 사전 시퀀스 순서에 안맞는거 같아요;;

ParkPD

아이디어.

이미 찾아본 단어에 대해서는 더 이상 찾을 필요가 없다.
사전순으로 찾아보면 된다.
가장 높은 값을 유지한다. (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 */

CynicJJ

많이 늦었습니다. ㅋ

!StepLadder.vb

    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

Word.vb

    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

!StepLadderTest.vb

    <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

algorithm edit step ladder - andstudy/forge GitHub Wiki

Outbreak

문제 요약

문제 해결

계획

풀이

문제 질문

ParkPD

CynicJJ

!StepLadder.vb

Word.vb

!StepLadderTest.vb

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️