找到真正的詞的迴文

我剛纔讀了Anagram of a Palindrome這個問題，這引出了我一些其他的迴文問題。但是當我想到一個迴文時，我想到了真實世界的迴文，它們使用一種語言的真實詞彙，並在該語言中具有某種程度的意義。找到真正的詞的迴文

因此，如果我們放棄過於困難的語法和意義，我們是一個很好的算法來發現由字典中的單詞組成的迴文序列？您可以將字典預處理爲一個數據結構，使其更容易。除非您有辦法在現實的計算時間和空間中執行此操作，否則無法通過查找每個可能的迴文來預處理字典。

假設您想要查找多達100,000個字符的迴文，並且您有一個包含100,000個小寫英文單詞的字典。

獎勵積分如果你能想出一種方法來快速找到迴文的anagrams以及。我不確定是否有可行的方法來做到這一點。

編輯 - 似乎有一些混亂，所以我一定不清楚。我正在尋找回文序列（長度可達100,000個字符），而不是單個字典字，這是一個微不足道的問題。所以，任何數量的「a」或「i」都是迴文，因爲每一個都是單詞，順序是迴文。「amanaplanacanalpanama」也是一個迴文，因爲「a」，「man」，「plan」，「canal」和「panama」是單詞（如果「panama」真的在這本字典中）

來源

2011-12-09 psr

這是面試還是問題？ –

有多少實際字詞包含多達100,000個字符？ –

@ DMactheDestroyer我相信他的意思是說，如果我們把語法的語境拿出來是沒有意義的，那麼你可以把真正的作品結合到字典中去形成長達100,000個字符的迴文。 –

在C＃中，使用LINQ改造給出的字符串...

public bool isPalindrome(string str){ 
    var rev= new string(Enumerable.Range(1, str.Length).Select(i => str[str.Length - i]).ToArray()); 
    return String.Compare(str, rev, true); 
}

這部分很簡單，但如果你要攻擊10萬米字的長度將採取一些優化性能。人們可以將琴絃切成兩半，然後翻轉下半部分以加速反轉過程並縮短比較琴絃。

從那裏，我會將每個發現的迴文轉儲到IEnumerable集合中，並根據預先定義的字典對它們進行測試......再次，我沒有提到的關鍵是性能。

編輯：更好的性能選項（信貸http://www.softwareandfinance.com/CSharp/Palindrome.html）

static bool IsPalindrome(string s) 
{ 
    bool palindrome = true; 
    for (int i = 0; i < s.Length/2 + 1; i++) 
    { 
     if (s[i] != s[s.Length - i-1]) 
     { 
      palindrome = false; 
      break; 
     } 
    } 
    return palindrome; 
}

這種方法假定這個詞是一個迴文（可能是危險的），但直到有不匹配比較信串的字母。奇怪的字母詞照顧。在我上面的方法中，分裂一半你必須抓住半+ 1來比較蘋果和蘋果。

你在找什麼？

來源

2011-12-09 18:47:36

這並不是要找出字典中所有單詞都是迴文的，這是微不足道的，而是要找到所有字母順序最多爲100,000個字符的迴文。所以，任何數量的「a」或「i」都是迴文，因爲每一個都是單詞，順序是迴文。「amanaplanacanalpanama」也是一個迴文，因爲「a」，「man」，「plan」，「canal」和「panama」是單詞（如果「panama」真的在這本詞典中）。 – psr

你說你想找到迴文並檢測它們是否是字典中的「真正的單詞迴文」。我不確定我是否理解你的問題。如果你想在迴文中找到「真正的字典單詞，那麼你會檢查你的字典中的每個單詞，如果該字符串包含字符序列 - 但這與迴文本身無關。」 –

我想檢測是否一個給定的字符串是一個由給定字典中的單詞組成的迴文，我希望該算法高效。我怎樣纔能有效地判斷「amanaplanacanalpanama」是否是迴文？請注意，如果「巴拿馬」不是在字典中（根據我對迴文的定義，它不僅要求字符串是可逆的，而且要求字符都是雙向的） – psr

我在想，如果我真的想在運行時有效地檢查字典而犧牲一些編譯時的工作，那麼我會建立一個狀態機來檢查字典序列是否在字典中。我可以通過閱讀每個字典條目來建立這個，然後逐字逐字地創建一個新的狀態（如果不存在的話）。

因此，如果字典中的第一個單詞是「a」，則在讀取「a」時從開始狀態變爲「a」狀態將是有效的過渡。如果下一個單詞是「ax」，我會在「x」上創建從「a」到「ax」的過渡，並在「e」上創建從「ax」到「ax」的過渡。國家「a」和「ax」將是接受國，但不是「ax」。

這將是一個非確定性狀態機，允許從任何接受狀態到開始狀態的轉換（因爲在閱讀「ax」之後，我可能會讀取「a」，而「axea」使用字符串語言完整的詞可以在字典中找到）。然後我會使用衆所周知的技術（確實使用別人的代碼，因爲這段代碼肯定被寫入了1000次以上）將狀態機優化成確定性狀態機。

在運行時，我會通過狀態機向前運行可能的迴文，如果它向前傳遞，則向後。

我不知道什麼是一個很好的方法來找到迴文的anagrams。

來源

2011-12-09 19:32:50 psr

找到真正的詞的迴文

回答

相關問題